백준 2156 포도주시식

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

2156번: 포도주 시식

 

동적계획법에 좀 익숙해지나 했는데.... 여전히 어렵다. 꼭 동적계획법 유형의 문제는 다시한번 혼자힘으로 다시 풀어보아야 겠다.

 

계단 오르기 문제와 비슷한 유형이라고 생각했지만 현재 포도주를 안마시는 게 더 큰 값을 가질 수 있다는 것까지 생각해주어야 했다. 점화식을 표현해보면

 

 

 dp[i] = MAX(dp[i-1], dp[i-2]+ar[i] , dp[i-3]+ar[i-1]+ar[i]);

 

 

개인적으로 마지막 dp[i-3]+ar[i-1]+ar[i] 을 생각해내는게 어려웠던 것 같다. 결국 블로그를 참고하여 문제를 풀었지만 다음 번에 풀 떄 꼭 스스로의 힘으로 풀고싶다! 그리고 또 하나 배운점이 있다면 이번 dp문제는 3번째 이전에 사용된 값도 이용 되었기 때문에 초기값을 직접 넣어주는것 보다 차라리 크기를 n+3만큼 늘려서 문제를 해결하는게 간결하게 코드를 작성 할 수 있다는 것을 배웠다. 

 

풀이

package 동적계획법;
 
import java.io.*;
 
public class 포도주시식 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] ar = new int[n +3];
        int[] dp = new int[n+3];
        for (int i = 3; i < n+3; i++) {
            ar[i] = Integer.parseInt(br.readLine());
        }
 
 
        for(int i = 3;i<n+3;i++){
            dp[i] = Math.max(dp[i-2]+ar[i],dp[i-3]+ar[i-1]+ar[i]); //점화식
            dp[i] = Math.max(dp[i-1],dp[i]); //현재차례의 주스를 선택안하는 것이 더 손해인 경우생각
        }
        System.out.println(dp[n+2]);
    }
}