https://www.acmicpc.net/problem/2559
문제
> 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때,
연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
> 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,
3 -2 -4 -9 0 3 7 13 8 -3
모든 연속적인 이틀간의 온도의 합은 아래와 같다.
> 이때, 온도의 합이 가장 큰 값은 21이다.
> 또 다른 예로 위와 같은 온도가 주어졌을 때,
모든 연속적인 5일 간의 온도의 합은 아래와 같으며,
이때, 온도의 합이 가장 큰 값은 31이다.
> 매일 측정한 온도가 정수의 수열로 주어졌을 때,
연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.
접근
누적합으로 풀 수 있다.
주어진 측정된 온도들을 입력을 받으며 누적합의 초기값을 만들기 위해 주어진 K개의 온도를 합해서 저장해 둔다.
이 초기값을 이용해 각각의 K개의 합을 구한다면
sum(i)는 sum(i-1)번째에서 온도(i-1)번째를 빼고, 추가로 num(i-1+K)를 더해주면 된다.
문제해결
> N과 K를 입력받고 측정한 온도 N개를 num배열에 저장하며, 누적합을 저장할 rst배열을 만든다.
> rst배열의 크기는 K의 값에 따라서 N-K+1개의 결과를 가지게 된다.
> 1-based로 인덱싱하기 위해 0번째를 주고 N개의 온도를 입력받으며 rst의 초기값인 1번을 미리 누적한다.
> 만든 rst(1)을 이용해 rst(2)번부터 주어진 k를 고려해 누적합을 구한다.
> 누적합을 구하며 rst(1)을 기준으로 최대값연산으로 최대의 값을 구한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//2559번 수열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] num = new int[N+1];
int[] rst = new int[N-K+2];
num[0] = rst[0] = 0;
for(int i = 1; i <= N; i++) {
num[i] = Integer.parseInt(st.nextToken());
if(i <= K) rst[1] += num[i];
}
int Max = rst[1];
for(int i = 2; i <= N-K+1; i++){
rst[i] = rst[i-1] - num[i-1] + num[i-1+K];
Max= Math.max(Max, rst[i]);
}
System.out.print(Max);
}
}
후기
누적합의 규칙을 인덱싱 하는게 좀 생각할 수 있는 시간을 요헀다.
