동적계획법_2156_포도주시식

 

오늘은 백준 단계별로 문제풀기 동적계획법1에 분류되어 있는 다이나믹 프로그래밍 문제를 풀이해보겠다. 같은 카테고리에 존재하는 계단오르기 문제와 아주 비슷한 문제이다. 그 문제를 풀때는 점화식을 어떻게 구해야 할지 몰라서 다른 사이트를 참고했는데 참고한 사이트 주소는 아래의 링크를 걸어두겠다. 

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

2156번: 포도주 시식

연속해서 세개의 와인을 먹으면 안되기 때문에 연속해서 선택하는 수가 2를 초과하면 안된다. 

시작하기에 앞서 경우의 수를 크게 나누면 가장 마지막 와인을 먹는 경우와 먹지않는 경우로 나누어서 생각해본다. 마지막 와인을 먹지 않는다면, 마지막 바로 직전의 와인을 먹는 경우를 생각해야 한다.(1)

마지막 와인을 먹는 경우를 생각해보자. 단순하게 생각해서  i번째 와인을 먹으려고 할 때, i-1번째 와인을 먹은 경우를 저장한 메모이제이션 값을 더하도록 점화식을 작성하게 되면 i-1번째 와인 또한 같은 방식으로 i-1번째 와인을 먹은 경우를 더하기 때문에 결론적으로는 i, i-1, i-2번의 와인 즉, 연속된 세개의 와인을 먹는 경우의 수가 점화식에 포함되기 때문에 다른 방법을 고려해보아야 한다.

그렇다면 직관적으로 생각해서, 현재 i번째 와인을 먹는다고하면  가장 마지막으로 먹은 와인이 i-2번째인 경우와 i-3번째인 경우를 생각해보아야 한다.

(2) i-2번째 와인을 먹은 경우를 메모이제이션한 값에 i번째 와인을 먹는 경우의 수를 더한다. 

ㄴ> dp[i-2] + wine[i]

(3) i-3번째 와인을 먹은 경우를 메모이제이션 한 값에 i-1번째 와인을 먹는 경우의 수와 i번째 와인을 먹는 경우의 수를 더한다. ㄴ> dp[i-3] + wine[i-1] + wine[i]

위의 강조 표시한 (1), (2), (3)의 값 중에서 최댓값을 찾아서 메모이제이션 하면서 bottom-up하다가 마지막에 배열의 끝 값을 출력한다. 

 

[ 소스코드 ] 

package DynamicProgamming;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _2156_포도주시식 {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        int wine[] = new int[n+1];
        int dp[]   = new int[n+1];
        
        
        for(int i=1; i<=n; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }
        
        //바틈업 -> 초깃값 초기화하기
        dp[1] = wine[1];
        
        if(n > 1) { //n=1일때, dp[2]를 채우려고 하면 outof index에러발생
            dp[2] = wine[1] + wine[2];
        }
        
        for(int i=3; i<=n; i++) {
            //우리가 구해서 메모이제이션 해야하는 값은 모든 경우의 수 중에서 최댓값이다.
            dp[i] = Math.max( dp[i-1] , Math.max(dp[i-2] + wine[i], dp[i-3] + wine[i-1]+ wine[i]));
 
        }
            
        
        System.out.println(dp[n]);
    }
 
}

 

참고 : https://st-lab.tistory.com/135