[백준 *Java] - 포도주 시식 (2156)

 

포도주 시식 문제보기

2156번: 포도주 시식

 

문제 설명
효주는 포도주 시식회에 갔다.
그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다.
효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로, 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다.
1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고,
각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때,
효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어,
6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때,
첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 <= n <= 10,000)
둘째 줄부터 n+1번째 줄까지  포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다.
포도주의 양은 1,00 이하의 음이 아닌 정수이다.

출력
첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

---

👇  접근방식

기존에 내가 알고 있던 DP랑은 확실히 다르게 경우의 수가 엄청 많다..

이걸 어떻게 점화식으로 잡을 수 있을까?

배열을 더 많이써야할까라는 생각을 했지만, 여러 변수를 잡아야하는 거 같아 쉽게 생각나지 않는다.

일단 현재 테스트케이스를 보면 [6, 10, 13, 9, 8, 1] 총 6개를 가지고 일단 경우의 수를 먼저 확인해본다.

N이 1일 때?  1개이다. (초기화)

N이 2일 때? 1개이다. (초기화)

N이 3일 때? 3개이다.

O	X	O
O	O	X
X	O	O

N이 4일 때? 3개를 비교해주어야 한다.

O	X	O	O
O	O	X	O
X	O	O	X

N이 5일 때?

O	O	X	O	O
O	X	O	O	X
X	O	O	X	O

 

처음에 계속 이것저것 적어가면서 경우의 수를 확인하는데 너무 많았습니다.

그러다가 이제 포기하고, 블로그 작성할 겸 테이블 표를 작성해서 O,X를 써보니

처음에 제가 종이랑 펜에다가 적을 때, 그냥 무작정 경우의 수만 나열을 했었는데

적어보니 경우의 수가 3개 한정으로 딱 떨어집니다.

그 이유가 다른 경우의 수는 저 세 경우의 수에 겹쳐 생략이 가능합니다.

문제(포도주의 양은 1,000 이하의 음이 아닌 정수)에 나온대로 한다면 확실히  세개 한정으로 경우의 수로 줄어들어 점화식을 만들 수 있을 수 있습니다.

OOX

OXO

XOO 

로 점화식을 찾아보도록 하겠습니다.

---

점화식을 구하기 위해서 종이에 글을 쓴 내용을 테이블 표로 그려서 설명하겠습니다.

	0	1	2	3	4	5
XOO	6	10	13	9	8	1
OXO	6	10	13	9	8	1
OOX	6	10	13	9	8	1

일단 표로 설명을 드리면,

먼저 인덱스 2까지 초기화를 해주어야, 규칙을 만들 수 있습니다.

DP 테이블에다가 

0, 1, 2 를 초기화를 해줍니다.

0 => 6

1 => 16

2 => 23

이렇게 됩니다.

인덱스 3을 구하기 위해서는, 

XOO는 10+13으로 DP[2]에 들어가있는 값으로 초기화 해줍니다.

OXO는 색이 칠해져있는 관계로 9를 더해줘야하며, 뒤에있는 두 13, 6까지 더해주어야합니다. 따라서, DP[0] + arr[3] + arr[2]

OXX는 이것도 위와 동일하게,  DP[1] 은 6+10이 들어가있으니, DP[1]과 arr[3]을 더해주면 됩니다.

이런식으로 점화식 규칙을 따르면됩니다.

아래는 성공한 코드입니다.

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

public class Boj_2156 {
    static int [] DP;
    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+1];
        DP = new int[N+1];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 초기화
        DP[0] = arr[0];
        DP[1] = arr[0] + arr[1];
        if (N > 2) DP[2] = Math.max(Math.max(arr[0]+arr[1], arr[0]+arr[2]), arr[1]+arr[2]);



        // 루프DP
        for (int i = 3; i < N; i++) {
            DP[i] = Math.max(DP[i-1], Math.max(DP[i-2]+arr[i], DP[i-3] + arr[i] + arr[i-1]));
        }

        System.out.println(DP[N-1]);
    }
}