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

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

2156번: 포도주 시식

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[10001];
        int[] dp = new int[10001];

        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];

        for(int i=3; i<=n; i++){
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2], dp[i-3]+arr[i-1])+arr[i]);
        }

        System.out.println(dp[n]);
    }
}

 

 

 

계단 오르기 문제와 비슷하다 생각해서 거의 똑같이 코드를 쓴후 dp중 최댓값을 구하는식으로 하려 했지만 

알고보니 다른점이 있었다.

계단 오르기 문제는 무조건 마지막 계단을 밟아야 한다는 조건이 있었지만 이문제는 아니다. 

그말은 즉, 이문제에서는 점화식을 구할 때 dp[i]가 i번째 와인인 arr[i]를 반드시 선택할 필요는 없는 것이다.

 dp[i]를 구할 때 arr[i]을 포함하는 경우에서의 최댓값과 arr[i]를 포함하지 않는 최댓값인 dp[i-1]랑 비교를 해야한다.

 

세개의 값을 연속해서 더하면 안된다는 것은 계단 오르기 문제와 같으므로 같은 방법으로 

dp[i-3]+arr[i-1]+arr[i] 과 dp[i-2]+arr[i] 의 최댓값을 구한다음에, 

dp[i-1]랑도 비교해주면 된다. 

 

DP는 막상 적고나면 코드는 짧은데 이 한줄의 점화식을 세우는게 참 어렵다..^^