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

흶·2021년 7월 1일

Algorithm

목록 보기

7/60

문제

BOJ 2156 : 포도주 시식 - https://www.acmicpc.net/problem/2156

풀이

와인 3잔을 연속해서 마실 수 없기 때문에 현재 위치에서 OOX, OXO, XOO의 경우 중 어떤 것이 가장 많이 먹을 수 있는 경우인지 판단해가면 된다. (맨 오른쪽이 현재 위치가 된다. 현재 위치를 기준으로 하나 전, 두개 전 경우를 보면 된다.)

예시를 보자면, 현재 인덱스 i가 2일때 다음과 같은 경우의 수가 만들어진다.

<OOX>

와인 순서	0	1	2	3	4	5	6
선택 여부	O	O	X

<OXO>

와인 순서	0	1	2	3	4	5	6
선택 여부	O	X	O

<XOO>

와인 순서	0	1	2	3	4	5	6
선택 여부	X	O	O

먼저 int[] dp 배열을 만든다.

OOX : dp[i-1]
OXO : dp[i-2] + wines[i]
XOO : dp[i-3] + wines[i-1] + wines[i]

위 세 가지 경우 중 가장 max값을 dp[i]에 저장한다. 최종적으로 dp[n-1]에 저장되는 수가 마실 수 있는 와인의 최댓값이 된다.

dp[0]과 dp[1], dp[2]는 예외처리 해준다.

dp[0]은 wines[0] 자체가 최댓값이 된다.
dp[1]은 wines[0] + wines[1]가 최대값이 된다.
dp[2]는 Math.max(dp[1], wines[0]+wines[2], wines[1]+wines[2])를 구한다.

코드

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

        int[] dp = new int[n];
        dp[0] = wines[0];

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

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

정리

✔ 알고리즘 분류 - 다이나믹 프로그래밍
✔ 난이도 - ⚪ Silver 1

🤦‍♀️ 오늘의 메모

DP는 할때마다 어떻게 풀어내야 할지 생각하는게 너무 어렵다.. 일단 시간초과가 예상되면 DP를 한번 생각할 것. DP는 memorization과 점화식이 key point! memorization을 어떻게 해서 중복 연산을 줄일 것인지를 잘 생각해보자.
n의 범위가 1부터이기 때문에 처음에 요렇게 0, 1, 2를 밖에다 해주어서 index에러가 났다. 범위 잘 보자!

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