백준 - 2559번(수열)

문제 출처: https://www.acmicpc.net/problem/2559

문제

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

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

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

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

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

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

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int K = Integer.parseInt(tokenizer.nextToken());
        tokenizer = new StringTokenizer(reader.readLine());
        int[] temp = new int[N];
        for (int i = 0; i < N; i++) {
            temp[i] = Integer.parseInt(tokenizer.nextToken());
        }

        int answer = Integer.MIN_VALUE;

        int sum = 0;

        // 최초 합
        for (int i = 0; i < K; i++) {
            sum += temp[i];
        }

        answer = Math.max(answer, sum);

        for (int i = 1; i <= N - K; i++) {
            sum = sum - temp[i - 1] + temp[i + (K - 1)];
            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }

}

• 연속하는 K일의 수 중 최대를 구해야한다.
• 우선 처음부터 K개의 합을 구한다.
• 그 다음 한 칸씩 이동하며 왼쪽의 값은 빼고 오른쪽의 값은 더하면서 최댓값을 찾는다.
• 처음에 문제를 잘못 이해하여 시간이 매우 오래 걸렸다...