[BOJ_2156] 포도주 시식

설명

---

계단 오르기 문제와 유사하다고 생각이 들었고 정말로 비슷하게 점화식을 수행하였습니다.

 

다만, Case가 연속된 3 Case를 구현하여야 하기 때문에 이전의 한 계단, 두 계단만 고려하던 연속적인 부분을 3케이스로 나누어서 선택하였습니다. 하나는 모두 3개를 선택하는 경우, 이전의 연속된 2개만 선택하는 경우, 현재 케이스를 스킵합니다.

 

헷갈릴 수 있는 부분이 제가 wine 배열은 N 개로 짜서 코드를 볼 때 인덱스 위치가 다르다는걸 감안해주셔야 합니다.

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 계단 오르기 문제와 비슷하여 접근이 쉬웠습니다.
 */
public class BOJ_2156 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int N = Integer.parseInt(tk.nextToken());
        int[] wine = new int[N];
        for (int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine()," ");
            wine[i] = Integer.parseInt(tk.nextToken());
        }
        int[] dp = new int[N + 1];
        dp[1] = wine[0];
        if(N >= 2) {
            dp[2] = dp[1] + wine[1];
            if(N > 2) {
                for (int i = 3; i <= N; i++) {
                    dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + wine[i - 1], dp[i - 3] + wine[i - 2] + wine[i - 1]));
                }
            }
        }
        System.out.println(dp[N]);
    }
}

 

2156번: 포도주 시식