[Baekjoon] 2156번 포도주 시식

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

 

설명 :

특정 조건 하에 고를 수 있는 최댓값을 찾는다.

유명한 배낭 문제(knapsack problem)와 비슷하다.

 

다이나믹 프로그래밍을 할 때 가장 중요한 것은 memoization 과 점화식(순환식)이다.

순환식을 먼저 만들어보자.

f(n) 이라는 가상의 함수가 있는데,

이 함수는 n개의 포도주들을 있을 때, (문제에서 주는 조건 하에) 가장 많이 마시는 포도주의 양을 반환한다.

문제에서 주어진 조건은, "연달아 세 잔을 마시면 안 된다" 이다.

 

문제에서 주어지는 예시로 설명을 이어가보자.

시음회에 온 나는 최대한 많은 포도주를 마시고 가려고 혈안이 되어있다.

시음할 수 있는 포도주로 총 6잔이 제공되었다.

나는 어떤 조합으로 잔을 선택해야 가장 많은 양을 마실지, 모든 경우의 수를 계산 할 것이다.

다이나믹 프로그래밍 관점에서, 마지막 잔에 내가 위치해있다고 생각해보자.

내가 선택할 수 있는 방법의 수는 총 3 개이다.

 

1. 마지막 잔(여섯번째 잔)을 마신다. (다섯번째 잔은 마시지 않는다)
2. 여섯번재와 다섯번째 잔을 마신다. (네번째 잔은 마시지 않는다)
3. 마지막 잔(여섯번째 잔)을 마시지 않는다. (다섯번째 잔이 마지막 잔이라고 생각하고 다시 계산한다)

 

위의 경우의 수 중에서 가장 양이 많은 것을 선택해야 한다.

 

따라서 아래와 같은 식을 하나 만들 수 있겠다.

 

glass[] //포도주 정보가 담긴 배열 f(n) = max(            f(n-2) + glass[n] , // 마지막 잔(여섯번째 잔)을 마신다. (다섯번째 잔은 마시지 않는다)            f(n-3) + glass[n] + glass[n-1] , // 여섯번재와 다섯번째 잔을 마신다. (네번째 잔은 마시지 않는다)            f(n-1) // 마지막 잔(여섯번째 잔)을 마시지 않는다. (다섯번째 잔이 마지막 잔이라고 생각하고 다시 계산한다)         )

 

이것이 이 문제의 점화식 되시겠다.

 

이 점화식이 계속 실행된다면 처음에 어떻게 채우느냐가 또 관건이 되는데,

그건 base case 로 우리가 직접 정해줘야 한다.

 

즉,

f(0) 은 포도주가 아예  없으므로 f(0) = 0

f(1) 은 포도주 한 잔 밖에 없으므로 이거라도 마셔야 최대가 되니까 f(1) = glass[1]

f(2) 은 포도주 두 잔 밖에 없으므로 둘 다 마셔야 최대가 되니까 f(2) = glass[1] + glass[2]

 

이 base case 를 염두해두고 코드를 작성하면 된다.

 

memoization 을 위해 n 크기만큼의 array 하나를 준비한 다음,

bottom up 방식을 좇아 i=1 부터 i=n 이 될 때까지 차근차근 위의 식 대로 올라가면 된다.

아래 코드에서는 i=1,2 인 경우를 직접 제시해줬기 때문에 i=3부터 시작한다.

 

마지막에 반환하는 값은, 우리가 알고싶은 "n개의 포도주들 중 가장 많이 마시는 포도주의 양" 이므로 f(n) 을 반환한다.

 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
        
		Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        if(n<=1) { //포도주가 하나 이하만 있는 경우 
        	System.out.println(scan.nextInt());
        	return;
        }
        
        int m[] = new int[n+1]; //포도주 양 
        int c[] = new int[n+1]; //cache(memoization)
        for(int i=1; i<=n; i++){
        	m[i]=scan.nextInt();
        }
		c[1]=m[1]; //base case
		c[2]=m[1]+m[2]; //base case
		int max = -1;
		for(int i=3; i<=n; i++){
			int temp = c[i-2]+m[i]; // 하나만 마시는 경우
			if(max<temp) max = temp;
			temp = c[i-3]+m[i]+m[i-1]; // 두 개 연달아 마시는 경우
			if(max<temp) max = temp;
			temp = c[i-1]; // 안 마시는 경우
			if(max<temp) max = temp;
			
			c[i]=max;
		}
		System.out.println(c[n]);
        
    }
}

 

코드 : http://boj.kr/49c6553130c6428e831d0389691fa973