백준 2156 포도주 시식 Java

정답률 34퍼센트의 dp문제 포도주 시식이다.

1부터 n번까지의 포도주를 3잔연속으로 마시지 않는 규칙을 지키고 마실 수 있는

포도주 양의 최대값을 구하는 간단한 문제이다.

 

하지만 점화식은 간단히 생각할 수 없었다.

항상 마지막자리의 앞자리에 어떤 수들이 올 수 있는지를 생각해야 한다.

알면서도 틀리는건 왜일까.

 

쨋든 이 문제에서 마지막 자리인 n번째에 올 수 있는 경우의 수는 세가지이다.

1. 안 마실 때

2. 한 번 연속으로 마시는 잔일 때

3. 두 번 연속으로 마시는 잔일 때

 

세 번 연속으로 마시는 잔일 때는?이라고 생각할 수 있지만

점화식을 통해 세 번 연속으로 마시지 않게 처리하는 것이다.. 

 

1. 안 마실 때

dp[n] =dp[n-1];

안마시니까 그 전 잔의 값을 가져오면 된다.

 

2. 한 번 연속으로 마시는 잔일 때

dp[n] = dp[n-2]+포도주[n];

첫 번째 잔이기 때문에 지금 먹는 포도주의 값과 전전인 dp[n-2]의 값을 포함시킨다.

 

3. 두 번째로 마시는 잔일 때

dp[n] = dp[n-3]+포도주[n-1]+포도주[n];

두번째로 마시는 잔이기 때문에 지금 마시는 잔과 전에 마셨던 잔과 전전전인 n-3의 값을 포함시킨다.

n-2의 값은 마시면 연속으로 세 잔이기 때문에 규칙에 위배된다.

 

이렇게 점화식을 짜면 어떠한 경우에도 세 잔을 연속으로 마신 경우는 없다.

이렇게 dp[n]에는 세 개의 경우중 가장 큰 값을 넣어 주면 된다.

 

예제에서 나온 값 {6 10 13 9 8 1}을 기준으로 조금만 살펴보자.

점화식에 n-3 까지 나오기 때문에 dp[2]까지는 답을 넣어줘야 한다.

dp[1] = 6

dp[2] = 6+10 = 16 이다.

dp[2]에서 나올 수 있는 최대값은 6+10 이기 때문에 포도주[1]+포도주[2]인 16이 들어가는게 맞다.

 

dp[3] 일때 Math.max(dp[2], Math.max(dp[1]+포도주[3], dp[0]+포도주[2]+포도주[3]))이 된다.

점화식은 참 어렵다. 나만 어려워 하는 것 같다.

또 주의 할 점이 n이 1부터 들어 올 수 있기 때문에 

dp[2]에 미리 답을 넣어주는 코드를 처리해야한다.

 

if(n>1)

 dp[2] = a[1]+a[2]

 

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] a = new int[n+1];
        int [] dp = new int[n+1];
        
        for(int i=1; i<=n; i++)
            a[i] = scan.nextInt();
        
        dp[1] = a[1];
        if(n>1)
            dp[2] = a[1]+a[2];
        
        for(int i=3; i<=n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+a[i], dp[i-3]+a[i-1]+a[i]));
        }
        
        System.out.println(dp[n]);
    }