★ 백준/2559 수열 / 누적합,로직의 최악의 연산횟수 제대로 구하기

수열

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

26858

9862

8013

36.378%

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다. 

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며, 

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오. 

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다. 

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

예제 입력 1 복사

10 2
3 -2 -4 -9 0 3 7 13 8 -3

예제 출력 1 복사

21

예제 입력 2 복사

10 5
3 -2 -4 -9 0 3 7 13 8 -3

예제 출력 2 복사

31

---

 풀이

/*
다이나믹 프로그래밍을 이용한 연속합문제에서 몇개를 연속해서 더할지를 알려준 문제같다고 생각했지만
다들 이중반복문으로 풀이했다.
그냥 n,k의 최댓값인 10만떄문에 연산횟수가 10만 *10만일거라고 생각했다.
하지만 (n-k) * k 만큼의 연산이므로 최대연산수는 대략 10만회정도이다.
문제풀기전 어떤 로직으로 해야할지, 그 로직의 최악의 연산횟수는 어떻게 될지 제대로 생각해야겠다.
 */

 로직을 잘 생각하고, 최악의 연산횟수를 잘 구하여 

완전탐색으로 풀 수 있으면 풀어야한다.

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    다이나믹 프로그래밍을 이용한 연속합문제에서 몇개를 연속해서 더할지를 알려준 문제같다고 생각했지만
    다들 이중반복문으로 풀이했다.
    그냥 n,k의 최댓값인 10만떄문에 연산횟수가 10만 *10만일거라고 생각했다.
    하지만 (n-k) * k 만큼의 연산이므로 최대연산수는 대략 10만회정도이다.
    문제풀기전 어떤 로직으로 해야할지, 그 로직의 최악의 연산횟수는 어떻게 될지 제대로 생각해야겠다.
     */

    static int n;
    static int k;
    static int[] numbers;
    static int max = Integer.MIN_VALUE;


    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);
        numbers = new int[n];
        input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(input[i]);
        }

    }

    static void solve() throws IOException {
        for (int i = 0; i <= n - k; i++) {
            int sum = 0;
            for (int j = i; j < i+k; j++) {
                sum += numbers[j];
            }
            max = Math.max(max, sum);
        }
        bw.write(max+"");

    }


}

 

다른사람풀이

누적합으로도 풀이가능하다. 해당 인덱스까지 모든 값을 더한 누적합값을 가진 dp배열을 통해

2일씩 더한부분, 5일씩 더한 부분등  누적합값을 빼주면서 구한다.

import java.io.*;
import java.util.Arrays;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
     */
    static int n;
    static int k;
    static int[] dp;
    static int max = Integer.MIN_VALUE;


    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);
        dp = new int[n];
    }

    static void solve() throws IOException {
        memoization();

        //온도 최대값 구하기
        for (int i = k - 1; i < n; i++) {
            if (i - k < 0) {
                int temper = dp[i];
                max = Math.max(max, temper);
            } else {
                int temper = dp[i] - dp[i - k];
                max = Math.max(max, temper);
            }

        }
        bw.write(max+"");



    }

    static void memoization() throws  IOException{
        //dp 배열 채우기 -> 누적합 채우기
        String[] input = br.readLine().split(" ");
        dp[0] = Integer.parseInt(input[0]);
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + Integer.parseInt(input[i]);
        }
    }

}