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

백준 2156 포도주 시식 Silver I - JAVA 📌

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

문제 설명

문제 풀이

---

접근 💡

문제에서 주어진 조건 중 와인 3잔을 연속해서 마실 수 없다는 조건을 잘 생각해보자.

현재 위치에서 OOX, OXO, XOO의 경우를 생각해 볼 수 있는데, 이 경우 중에 어떤 경우가 제일 많이 먹을 수 있는 경우인지 판단해야 한다.

 

표로 그려 예시를 확인해보자. 현재 선택하고 있는 와인은 3번째 와인이라고 가정한다.

 

dp 배열을 만들어보자.

dp[1] = wine[1], dp[2] = wine[1] + wine[2]로 초기화 해준다.

 

 1. OOX 의 경우

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

 

이 경우에는 dp[i - 1]이 된다.

 

2. OXO의 경우

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

 

이 경우에는 dp[i - 2] + wine[i]가 된다.

 

3. XOO의 경우

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

 

이 경우에는 dp[i - 3] + wine[i - 1] + wine[i]가 된다.

 

위 세가지 경우 중 최댓값을 dp[i]에 저장한다.

-> dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + wine[i], dp[i - 3] + wine[i - 1] + wine[i])

 

이 때 N이 1과 2가 들어오는 경우는 예외처리를 해주어야 한다.

N이 1일 경우 최대는 wine[1]이 된다.

N이 2일 경우 최대는 wine[1] + wine[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[] wine = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }

        if (N == 1) {
            System.out.println(wine[1]);
            return;
        } else if (N == 2) {
            System.out.println(wine[1] + wine[2]);
            return;
        }

        int[] dp = new int[N + 1];
        dp[1] = wine[1];
        dp[2] = wine[1] + wine[2];

        for (int i = 3; i < N + 1; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + wine[i], dp[i - 3] + wine[i - 1] + wine[i]));
        }
        System.out.println(dp[N]);

    }
}