[백준]JAVA - 2156번: 포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

풀이

동적 계획법 (dp) = 다이나믹 프로그래밍으로 접근하면 되는 문제이다.

dp 관련 알고리즘은 해당 문제가 제시하는 조건에 맞는 점화식만 찾으면 쉽게 해결할 수 있다. 찾기가 어려울뿐... 

 

<조건>

1. 포도주 잔을 선택하면 무조건 다 마신 후에 제자리에 놓아야 한다.

2. 인접한 포도주를 3잔 연속으로 마실 수 없다. 

 

위 조건에 맞는 점화식을 발견하려면 최소 4번째 포도주까지 진행해봐야한다. 우선 포도주 양을 담을 wine 배열과 i번째 포도주에 도달했을 경우 최대 포도주 양을 담을 dp 배열을 생성했다고 가정하자.

 

dp[0] = wine[0];

dp[1] = wine[0] + wine[1];

dp[2] = Math.max(dp[1], Math.max(wine[0] + wine[2], wine[1] + wine[2])

 

2번째 포도주까지의 최대 양을 구하는 건 생각보다 쉽다. 하지만 포도주가 3개 이상일 때부터는 점화식을 적용해야한다. 

 

⑴ i번째 포도주를 마시지 않는 경우

⑵ i번째 포도주를 첫 번째로 마시는 경우

⑶ i번째 포도주를 두 번째로 마시는 경우

 

i번째 포도주에 도달했을 때 위처럼 총 3가지 경우가 생긴다. 하나씩 살펴보면 다음과 같다.

 

1. i번째 포도주를 마시지 않는 경우 

i-1번째 포도주에서도 위와 같이 3가지의 경우가 생기지만 i-1번째에 도달했을 때 최대 포도주 양이 될 것이다. 

dp[i-1]

 

2. i번째 포도주를 첫 번째로 마시는 경우

무슨 일이 생겨도 i-1번째 포도주는 마시지 않은 경우에 해당된다. 그렇기 때문에 i-2번째의 최대 포도주 양과 i번째 포도주 양을 더해주면 된다.

dp[i-2] + wine[i]

 

3. i번째 포도주를 두 번째로 마시는 경우

무슨 일이 생겨도 i-1번째 포도주는 마셨다. 다르게 말해서 i-2번째 포도주는 절대 마실 수 없다는 뜻이 된다. 그렇기 때문에 i-3번째의 최대 포도주 양과 i-1번째 포도주 양, i번째 포도주 양을 더하면 된다.

dp[i-3] + wine[i-1] + wine[i]

 

이제 모든 점화식이 완성되었으니까 이젠 적용하면 된다. dp는 i번째 포도주에 도달했을 때의 최대 포도주 양이다. 즉, 3가지 경우 중 제일 큰 값을 dp 배열에 넣어주면 된다. 

dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + wine[i-1] + wine[i], dp[i-2] + wine[i]));

 

<최종코드>

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
		
        int count = sc.nextInt();
        int[] wine = new int[count];
        int[] dp = new int[count];
	
        for (int i=0; i<count; i++) {
            wine[i] = sc.nextInt();
        }
		
        // 와인이 1개인 경우
        dp[0] = wine[0];
		
        // 와인이 2개 이상인 경우
        if (count > 1) {
            dp[1] = wine[0] + wine[1];
        }
		
        // 와인이 3개 이상인 경우
        if (count > 2) {
            dp[2] = Math.max(dp[1], Math.max(wine[0] + wine[2], wine[1] + wine[2]));
			
            for (int i=3; i<count; i++) {
                dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + wine[i-1] + wine[i], dp[i-2] + wine[i]));
            }
        }
		
        System.out.println(dp[count-1]);
    }
}