문제 해석
- 일단, 첫번째 줄에서 숫자의 개수(N) 개와 연속적인 K일(며칠간의 온도를 합할 건지!)를 입력받고, 두번째 줄에선 N개만큼의 숫자(=온도 값)를 입력받는다.
- 모두 입력 받았다면 N개의 숫자를 K기간 만큼의 누적합으로 시작점과 종료점을 +1만큼 증가시켜 더한다. (만약, 마지막 인덱스를 만났다면 반복은 멈춰야 함!)
- 문제의 흐름을 설명하면 아래와 같다.
[예시]
10 2
3 -2 -4 -9 0 3 7 13 8 -3
[답]
21
M = 10 K = 2 i*2 - K
[순서] 2일 단위로 더하는 경우
3 + (-2) = 1 | 인덱스 0 1
(-2) + (-4) = -6 | 인덱스 1 2
(-4) + (-9) = -13 | 인덱스 2 3
(-9) + 0 = -9 | 인덱스 3 4
0 + 3 = 3 | 인덱스 4 5
3 + 7 = 10 | 인덱스 5 6
7 + 13 = 20 | 인덱스 6 7
13 + 8 = 21 | 인덱스 7 8
8 + (-3) = 5 | 인덱스 8 9
dp에는 [1, -6, -13, -9, 3, 10, 20, 21, 5] 가 들어가고,
여기서, 최대 온도 값은 '21'이 된다.
[예시]
10 5
3 -2 -4 -9 0 3 7 13 8 -3
[답]
31
M = 10 K = 5
[순서] 5일 단위로 더하는 경우
3 + (-2) + (-4) + (-9) + 0 = -12 | 인덱스 0 1 2 3 4
(-2) + (-4) + (-9) + 0 + 3 = -12 | 인덱스 1 2 3 4 5
(-4) + (-9) + 0 + 3 + 7 = -3 | 인덱스 2 3 4 5 6
(-9) + 0 + 3 + 7 + 13 = 14 | 인덱스 3 4 5 6 7
0 + 3 + 7 + 13 + 8 = 31 | 인덱스 4 5 6 7 8
3 + 7 + 13 + 8 + (-3) = 28 | 인덱스 5 6 7 8 9
dp에는 [-12, -12, -3, 14, 31, 28]이 들어가고
여기서, 최대 온도 값은 '31'이 된다.
여기서 중요한 점은 어디에서 멈춰야하느냐인데 인덱스가 최고 N까지 도달했을 때 멈춰야한다
K가 2일 때는 총 9번의 누적합이 존재하고
K가 5일 때는 총 6번의 누적합이 존재한다.
즉, N - K + 1만큼 반복문이 수행된다는 것이다!
for(int i = 1; i <= N-K+1; i++) = for(int i = 0; i <= N-K; i++)
인덱스 증가 규칙을 살펴보면, 위의 반복문이 한번 돌 때마다 누적합을 진행해야하는데
반복문 한번을 돌때마다 시작점과 종료점이 모두 +1이 되어야하는데
현재 주어진 값에서 반복문을 돌때마다 +1하는 값은 i 뿐이다!
즉, i를 기준으로 i+K까지 반복한다고 볼 수 있다!
for(int j = i; j < i+K; j++)
이렇게 되면 K가 2일 때도 1 2 -> 2 3 -> 3 4 .. 형식으로 돌게 되고
K가 5일 때도 1 2 3 4 5 -> 2 3 4 5 6 -> 3 4 5 6 7 .. 같은 흐름!코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[] number;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //주어진 수의 개수(N)
int K = Integer.parseInt(st.nextToken()); //연속 일(K)
number = new int[N];
st = new StringTokenizer(br.readLine()); //숫자들 입력 받기
for(int i = 0; i < N; i++){ //배열에 숫자들 하나씩 넣기
number[i] = Integer.parseInt(st.nextToken());
}
int max = Integer.MIN_VALUE; //최댓값이 -(음수)가 나올 수도 있기 때문에
//N-K+1만큼의 반복문(시작이 1일때 기준)이 돌아야 하기 때문에 인덱스가 0일때는 N-K만큼만 돌면 됨!
for(int i = 0; i <= N-K; i++){
int sum = 0;
for(int j = i; j < i+K; j++){ //시작점의 위치와 종료점의 위치가 +1만큼 계속 이동하므로 i증가값에 맞춰 반복!
sum += number[j];
}
max = Math.max(sum, max); //최댓값을 계속 갱신
}
System.out.println(max);
br.close();
}
}결과
느낀 점
이 정도 난이도의 문제가 계속해서 나왔음 좋겠다...! 동적 계획법1할때와 다르게 풀만 한 것 같다...ㅎ 동적 계획법1이 개인적으로 좀 많이 어렵게 느껴져서 그런지...
