백준 2156 포도주 시식 python, java

문제를 보고 DP로 풀어야겠다 라고 생각이 들었다.
DP문제는 유형이 DP라는 것만 알면 훨씬 수월해지는듯..

📜 문제 바로 가기 : 포도주 시식

제출코드

파이썬

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))

DP = [[0, 0, 0] for _ in range(n)] # i번 잔까지 봤을때 연속으로 j번 마신경우 최대값

DP[0][1], DP[0][2] = arr[0], arr[0]

for i in range(1, n):
    DP[i][0] = max(DP[i-1])

    DP[i][1] = DP[i-1][0] + arr[i]

    DP[i][2] = DP[i-1][1] + arr[i]

print(max(DP[n-1]))

자바

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

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[n];
        for (int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int[][] DP = new int[n][3];
        for (int i=0; i<n; i++) {
            DP[i] = new int[]{0, 0, 0};
        }

        DP[0][1] = arr[0];
        DP[0][2] = arr[0];

        for (int i = 1; i<n; i++) {
            DP[i][0] = Arrays.stream(DP[i-1]).max().getAsInt();
            DP[i][1] = DP[i-1][0] + arr[i];
            DP[i][2] = DP[i-1][1] + arr[i];
        }

        System.out.println(Arrays.stream(DP[n-1]).max().getAsInt());

    }
}

---

접근방법

DP[i][j] 값의 의미는 i번째 포도주잔까지 고려를 했을때, 연속으로 마신 포도주잔이 j잔일때 최대값을 기록한다.

DP[i][0] 의 경우 연속으로 마진 포도주가 0이므로 i번째는 반드시 마시면 안되므로 이때의 최대값은 이전값 DP[i-1]에서 최대값을 가져온다.

DP[i][1] 의 경우 연속으로 마신 포도주가 이어져야함으로 i번째 포도주는 무조건 마셔야한다.
i번째를 마시고 연속잔이 1잔이 되야 함으로 DP[i-1][0] 에서 i번째 잔을 추가한다.

DP[i][2] 의 경우도 DP[i][1]처럼 i번째 포도주는 무조건 마셔야한다.
i번째를 마시고 연속잔이 2잔이 되야 함으로 DP[i-1][1] 에서 i번째 잔을 추가한다.