[BOJ] 2156 - 포도주 시식

[BOJ] 2156 - 포도주 시식

문제

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

• 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
• 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

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

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

입력

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

출력

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

예제 입력

6
6
10
13
9
8
1

예제 출력

33

문제 해결

지난 번에 계단 오르기와 유사한 문제이다. 점화식을 세워서 문제를 풀어보자.

index	0	1	2	3	4	5	6
wine	0	6	10	13	9	8	1
dp	0	0	0	0	0	0	0

아마 문제를 보면 이러한 배열을 설계했을 것이다. dp 배열에는 그 단계에서의 최대값을 저장하게 된다.

index가 1인 경우 최대값은 wine[1] 이다.

if i == 1 :
    dp[i] = wine[i]

index가 2인 경우 최대값은 dp[2-1] + wine[2] 이다.

elif i == 2:
    dp[i] = dp[i-1] + wine[i]

이제 index가 3인것 부터는 문제의 조건에 어긋나지 않는 최대값을 구해야 한다. 이떄 주의해야 할 조건은 "연속으로 놓여 있는 3잔을 모두 마실 수는 없다" 이다. index가 3일떄 dp[3-1]의 값은 1, 2를 거쳐 올라온 최대값(조건에 어긋남), 2만 거쳐서 온건지 불분명하다. 따라서 조건에 맞는 index-1 의 값은 dp[3-3]에서 wine[3-1]을 거치고 wine[3] 에 도달한 값이다. 점화식을 세워보자

index가 3인 경우 최대값

elif i == 3:
    dp[i] = max(dp[i-2]  + wine[i], dp[i-3] + wine[i-1] + wine[i])

나머지 경우도 index가 3인 경우와 똑같지만 조심해야 할점은 3칸 건너뛰어서 고르는 경우도 있다는 것이다. 와인을 시음할때 건너뛰는 수는 마음대로이므로 3뿐만 아니라 3이상도 건너뛸수 있지만 4부터는 2칸 2칸 건너 뛴것이 최대값이 되기 때문에 고려하지 않아도 된다.

index가 4 이상인 경우

else :
    dp[i] = max(max(dp[i-2]  + wine[i], dp[i-3] + wine[i-1] + wine[i]), dp[i-4] + wine[i-1] + wine[i])

이제 코드로 옮겨보자.

python 코드

n = int(input())
wine = [0] * (n+1)
dp = [0] * (n+1)
for i in range(1, n+1):
    wine[i] = int(input())

for i in range(1, n+1):
    if i == 1 :
        dp[i] = wine[i]
    elif i == 2:
        dp[i] = dp[i-1] + wine[i]
    elif i == 3:
        dp[i] = max(dp[i-2]  + wine[i], dp[i-3] + wine[i-1] + wine[i])
    else :
        dp[i] = max(max(dp[i-2]  + wine[i], dp[i-3] + wine[i-1] + wine[i]), dp[i-4] + wine[i-1] + wine[i])

print(max(max(dp[n], dp[n-1]), dp[n-2]))

Test Case

1
50
current answer :  50
---------------------------------
7
16
97
100
41
40
42
77
current answer :  316
---------------------------------
5
8
12
56
85
22
current answer :  149
---------------------------------
6
16
30
98
75
65
49
current answer :  242
---------------------------------
4
80
28
78
88
current answer :  246
---------------------------------

느낀점

이번 알고리즘 포스팅부터 Test Case 라는 것을 추가시켜 봤다. 귀찮으면 없앨수도 있다. 꼭 반례를 찾으셨으면 좋겠다. 그리고 내가 이해한 것을 글로 작성한다는 것이 너무 어렵고 힘들다.