[백준] 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문제 수월해질까...ㅜ

 

 

참고

https://velog.io/@yanghl98/백준-2156-포도주-시식

https://hees-dev.tistory.com/30