[Baekjoon] #2156 - 포도주 시식

입력 

6
6
10
13
9
8
1

연속적으로 3잔을 모두 마실 수 없다는 제한이 걸린 문제이다.

 

n번째에 제한을 두는 문제는 i번째를 기준으로 (i - 1), (i - 2), (i - 3).. 번째를 생각봐야한다.

 

n = int(input())
grape = [0]
sum = 0
for _ in range(1, n + 1):
    grape.append(int(input()))

dp = [0, grape[1]]

if n > 1:  # 포도주가 1잔일 수 있음
    dp.append(grape[1] + grape[2])

for i in range(3, n+1):
    dp.append(max(dp[i-1], dp[i-2] + grape[i], dp[i-3] + grape[i] + grape[i-1]))
# 차례로 이번 차례 시식 X, 이번, 전전 차례 시식, 이번, 이전 차례 시식

print(dp[n])

우선 포도주 양이 값이 담긴 grape 배열 및 dp 배열을 초기화 하면 다음과 같다. (편의를 위해 1번 인덱스부터 사용한다.)

grape	0	1	2	3	4	5	6
	0	6	10	13	9	8	1

 

dp	0	1	2	3	4	5	6
	0	6	16	23	...	...	...

시식 가능한 포도주가 2개 이상일 때 dp 배열에 값을 추가한다.

현재 dp 배열이 의미하는 바는 다음과 같다. 

• dp[0] - 아무 잔도 시식하지 않음 
• dp[1] - 첫번째 잔을 시식했을 때의 값 
• dp[2] - 첫번째, 두번째 잔을 연속으로 시식했을 때의 값

이제 for문을 돌며 3번째 잔부터 시식 결정을 한다.

 

3번째 잔을 시식할 때는 다음 값을 비교해 가장 큰 값을 dp 값으로 채워넣는다.

dp.append(max(dp[2], dp[1] + grape[3], dp[0] + grape[3] + grape[2]))

 

코드의 의미는 다음과 같다.

• dp[2] - 현재(즉, 3번째 잔) 잔을 시식하지 않은 상태를 의미한다. (== 첫번째, 두번째 잔을 연속으로 시식)
• dp[1] + grape[3] - 현재 잔을 시식하고 첫번째 잔을 시식한다.
• dp[0] + grape[3] + grape[2] - 바로 직전 잔, 현재 잔을 시식한다. 

이제 dp[3]에는 가장 큰 값인 23이 저장될 것이다. 이 값은 2, 3번째 잔을 연속으로 시식했을 때의 값이다.

 

 

4번째 잔을 시식할 때는 다음과 같다. 

dp.append(max(dp[3], dp[2] + grape[4], dp[1] + grape[4] + grape[3]))

• dp[3] - 현재(즉, 4번째 잔) 잔을 시식하지 않은 상태를 의미한다.
• dp[2] + grape[4] - 현재 잔을 시식하고 첫번째, 두번째 잔을 연속으로 시식한다.
• dp[1] + grape[4] + grape[3] - 첫번째 잔을 시식하고 바로 직전 잔, 현재 잔을 시식한다. 

n = 6 까지 반복문을 돌면 6잔 중에 최대로 마실 수 있는 포도주의 양이 가장 마지막 인덱스 값에 저장된다.