백준 - 포도주 시식(2156)

⭐문제링크

🚨문제 풀이시 주의점

1. 연속적으로 3잔 이상 마실 수 없다.
2. 마자믹 잔이 무조건적으로 포함되진 않는다.

이전에 포스팅 한 계단오르기 문제와 비슷한 문제이다.
다른 점은 마지막 경우가 무조건적으로 포함되지 않는다는 것이다. 이 부분이 헷갈려서 1차 시도는 실패했었다.

실패코드

public static int dp(int N){
    if(dp[N]==null) {
        dp[N] = Math.max(Math.max(dp(N - 2), dp(N - 3) + grapes[N - 1]) + grapes[N], 
                dp(N - 2)+grapes[N-1]);
    }
    return dp[N];
}

해당 문제의 경우의 수는 총 3가지로 생각했다.

• 본인 미포함

  * dp(N - 2) + grapes[N-1]

• 본인 포함

  * Math.max(dp(N - 2),   dp(N - 3) + grapes[N - 1]) + grapes[N]
  -> 본인 포함해 연속되지 않은 경우 vs 연속된 경우 로 나뉜다!

내가 틀렸던 부분은 바로 본인 미포함 부분의 코드였다.
grapes[N-1] 라는 부분은 사실 무조건 [N-1]을 포함한다는 의미이다. 그러나 이렇게 코드를 짤 경우, N-1의 경우가 사실 제외되어야 할 항목임에도 불구하고 무조건적으로 포함을 해버리고 만다.

🤯 그렇기 때문에 밑의 코드처럼 수정하게 되었다.

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


public class Main {
   static Integer[] dp;
   static int[] grapes;
   public static void main(String[] args) throws IOException {
      int N = init();
      System.out.println(dp(N));
   }

   public static int dp(int N){
       if(dp[N]==null) {
           dp[N] = Math.max(Math.max(dp(N - 2), dp(N - 3) + grapes[N - 1]) + grapes[N], dp(N - 1));
       }
       return dp[N];
   }

   public static int init() throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int N = Integer.parseInt(br.readLine());

       grapes = new int[N+1];
       dp = new Integer[N+1];

       for(int i=1; i<=N; i++){
           grapes[i]=Integer.parseInt(br.readLine());
       }
       dp[0] = 0;
       dp[1]=grapes[1];

       if(N>=2){
           dp[2] = grapes[1]+grapes[2];
       }

       return N;

   }

}