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

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

2156번: 포도주 시식

---

와인을 3잔 연속으로 마실 수 없기 떄문에 현재 인덱스에서 OOX, OXO, XOO의 경우 중 최댓값을 선택해야 한다

 

예시를 들자면 위와 같이 볼 수 있다

 

OOX = dp[i-1]

OXO = dp[i-2] + arr[i]

XOO = dp[i-3] + arr[i-2] + arr[i-1]

 

위와 같은 점화식으로 계산하면 되고 0, 1, 2번쨰 인덱스는 예외처리 해준다

dp[0] = arr[0];
dp[1] = arr[0] + arr[1];
dp[2] = Math.max(dp[1], Math.max(arr[0]+arr[2], arr[1]+arr[2]));

 

 

 

자바 코드)

package boj;

import java.util.Scanner;

public class boj2156 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = scanner.nextInt();
        }

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

---

참고)

https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-2156-%ED%8F%AC%EB%8F%84%EC%A3%BC-%EC%8B%9C%EC%8B%9D

[백준] 2156 : 포도주 시식 (JAVA)