[백준] DP - 2156번, 포도주 시식 (다른 풀이 봄)
* 공부 목표
DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052
문) 1~n까지의 포도주, 최대 연속 2잔 선택 가능할 때 마실 수 있는 가장 많은 양
입) 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
1. 테이블 정의 : 문제 요약
2. 점화식 정의
- D[j] = Math.max(D[j - 1], Math.max(D[j - 2] + grape[j], D[j - 3] + grape[j - 1] + grape[j]));
3. 초기값
- D[0] = grape[0];
- D[1] = grape[0] + grape[1];
- D[2] = Math.max(d[1], Math.max(grape[0]+grape[2], grape[1]+grape[2]));
풀이
초기값과 점화식이 어떻게 유도되었는 지를 설명하겠음.
여기서 grape 배열은 입력받은 포도주 양이고, dp 배열을 새로 만들어 저장하는 형태.
초기값
n=0, 자기 자신이 가장 큰 값.
n=1, 자기 자신과 직전 값이 가장 큰 값.
n=2, 값이 총 3개가 나왔으므로 연속 값은 2개만 가능하다는 제약에 걸림.
경우의 수를 구해보면 (oox, oxo, xoo) 3가지.
- oox : d[1] 값과 동일.
- oxo : grape[0] + grape[2] ...
고로 각 경우의 수 중 가장 큰 값이 D[2]의 값이 되도록 함.
점화식
n=3, 값이 총 4개임. 여전히 제약 조건에 걸림.
크게 2가지로 나눌 수 있는데 1) 현재 위치 미포함 2) 포함.
1) 현재 위치 미포함
- D[2]의 값과 동일. 현재 위치 값을 더하지 않은 D[j-1]
2) 현재 위치 포함 : 제약 조건을 만족하면서 o로 끝나는 경우의 수
- ooxo : D[1] 값 + 현재 값(D[j-2] + grape[j])
- oxoo : D[0] 값 + grape[2] + 현재 값 (D[j-3] + grape[j-1] + grape[j])
마찬가지로 이 3개의 경우 중 가장 큰 값이 D[3] 값이 되도록 함.
▶ D[j] = Math.max(D[j - 1], Math.max(D[j - 2] + grape[j], D[j - 3] + grape[j - 1] + grape[j]));
코드
import java.util.Scanner;
public class num_2156 {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] grape = new int[n+1];
int[] d = new int[n+1];
//포도주 양
for(int i=0; i<n; i++) {
grape[i] = sc.nextInt();
}
//초기값
d[0] = grape[0];
for(int j= 1; j<n; j++) {
if(j==1) {d[1] = grape[0] + grape[1];}
else if(j==2) d[2] = Math.max(d[1], Math.max(grape[0]+grape[2], grape[1]+grape[2]));
else {
d[j] = Math.max(d[j - 1], Math.max(d[j - 2] + grape[j], d[j - 3] + grape[j - 1] + grape[j]));
}
}
sc.close();
System.out.println(d[n-1]);
}
}(주의) 다음과 같이 빼서 쓰면 런타임 에러 난다(n=1일 때부터 index 에러 뜸).
//초기값
d[0] = grape[0];
d[1] = grape[0] + grape[1];
d[2] = Math.max(d[1], Math.max(grape[0]+grape[2], grape[1]+grape[2]));
for(int j=3; j<n; j++) {
d[j] = Math.max(d[j-1], Math.max(d[j-2] + grape[j], d[j-3] + grape[j-1] + grape[j]));
}
DP 계단문제랑 비슷하다고 하는데, 순서대로 안 풀어서인지 너무 어렵다...
언제쯤 DP문제 수월해질까...ㅜ
참고