1. 문제 링크 및 문제
https://www.acmicpc.net/problem/2616
2. 해결 방법 생각해보자 ...
소형기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구해야 하므로 => dp 사용
-> dp[소형기관차 3대][객차수] 생성
한 대의 소형 기관차가 최대로 끌 수 있는 연속적으로 이어진 객차의 수도 주어지므로 => 누적합 사용
( 3,4 연속된 객차의 손님 수를 알고 싶을 때 누적합[5] - 누적합[3] 하면 됨)
소형기관차가 3대 일 때 최댓값을 구해야 하므로!
1. 소형기관차가 1대일 때, 객차 1번부터 N번까지 중 연속된 M개의 객차 내에서 최댓값을 계산한다.
2. 소형기관차가 2대일 때, 소형기관차 1대일 때의 열차값과 중복되지 않게 비교하며 연속된 M개의 객차 내에서 최댓값을 계산한다.
3. 소형기관차가 3대일 때, 최댓값 출력
어려우니 예시로 이해하자.
💡 백준 예시 1로 이해
객차의 수(N) : 7, 손님의 수(arr) : 35 40 50 10 30 45 60 , 연속된 객차(M) : 2 이므로
우리는
- 2개의 객차씩 연결시켜 최댓값을 구하는 과정을 (소형기관차 1대가 끌 수 있는 최댓값)
- 3번 진행해야 한다. (소형 기관차가 3대가 끌 수 있는 최댓값)
1 . 그럼 우선 누적합을 구하고 ( sumArr[i] = sumArr[i-1] + arr[i] )
2,3연속객차 승객수를 알고싶을 때 sum[4]-sum[2] 으로 승객수를 빠르게 구할 수 있기 때문에 누적합을 사용한다.
- sum[4] = arr[0] + arr[1] + arr[2] + arr[3]
- sum[2] = arr[0] + arr[1]
sum[4] - sum[2] = (arr[0] + arr[1] + arr[2] + arr[3]) - (arr[0] + arr[1]) 이므로 = arr[2]+arr[3] 즉 객차2 객차3의 승객수 값을 알 수 있는 것이다.
2. 누적합을 사용하여 소형기관차가 1대일 때 최댓값을 구한다.
1대일 때의 최댓값은 연속된 객차를 2개씩 합하여 얻을 수 있는 최댓값이므로
( 여기서 j = M ~ 객차의 수) (M부터인 이유는 연속된 객차이므로)
최댓값 = sumArr[j]-sumArr[j-M]
똑같은 예시로 2,3 연속객차 승객수를 알고싶다고 하자.
sumArr[4]-sumArr[4-2]를 해주면 된다.
연속된 객차 수 == 2 만큼 빼면서 해당경우의 최댓값을 찾는것이다.
즉, 2개의 연속된 객차가 1개 일 때의 최댓값으로 1을 채운다.
그럼 2는? 2개의 연속된 객차가 2개일 때의 최댓값 이므로,객차2개+객차2개=4로,
dp[2][4] 부터 시작하겠지용
- 소형기관차가 2대, 객차 4번까지 봤을 때
현재 객차가 4번. 그럼 연결객차는 3-4번 객차 이므로,
이건 sum[4]-sum[2] 입니다.
(arr는 0부터 시작해서 연결객차가 3-4 일때, 객차2+ 객차3을 해야함)
그럼 이 sum[4]-sum[2] 에 3-4번 객차 이전까지의 최댓값을 dp에 더해주면,
연속된 객차가 2개일 때의 최댓값을 얻을 수 있습니다.
3-4 객차 이전은 어떻게 구하냐 하니,
그건 이미 dp[1] 소형기관차가 1대일 때 우리가 구해놓은 값을 적용해주면 됩니다. dp[1][4-2]로!
엥 ? dp[1][4-2] ? 이건 어떻게 나온 거죠?
소형기관차가 1대일 때 dp[1]
현재 객차 - 2 = 4-2 = [ 4 - 2 ] 연속된 객차이므로, 2대씩 건너가면서 봐야함.
만약 문제에서 연속된 객차가 3으로 주어졌다면 4-3 으로 계산했겠지요?
따라서 dp[2][4] = dp[1][2] + sum[4]-sum[2] 가 됩니다.
이해를 위해 색을 넣었는데, 넣고 보니 크리스마스같고 좋습니다
이렇게 3대일 때 까지 계산하면
이러한 DP 를 얻게 됩니다
3. 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] arr, sumArr;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N+1];
sumArr = new int[N+1];
dp = new int[4][N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1;i<N+1;i++) {
arr[i] = Integer.parseInt(st.nextToken());
sumArr[i] = sumArr[i-1] + arr[i];
}
M = Integer.parseInt(br.readLine());
for(int i=1;i<4;i++){
for(int j=M*i;j<N+1;j++){
dp[i][j] = Math.max(dp[i-1][j-M]+(sumArr[j]-sumArr[j-M]), dp[i][j-1]);
}
}
System.out.println(dp[3][N]);
}
}느낀점
누적합 + DP 문제는 어렵다.
