[백준] 2156번 - 포도주 시식 (DP) - 결과 포함

www.acmicpc.net/problem/2156

2156번: 포도주 시식

스스로 풀지 못해서 다른 분의 글을 참고했다.

mygumi.tistory.com/98

백준 2156번 포도주 시식 [DP] :: 마이구미

포도주의 양이 주어지고 마실 수 있는 규칙이 존재한다.

 

1. 선택하면 해당 잔의 포도주를 모두 마신다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

 

가장 많은 양의 포도주를 마시기 위해서는 일단 더 많은 양을 가진 잔을 최대한 많이 선택해야 한다.

 

일반적인 다이나믹 프로그래밍 문제와 같이 앞에서부터 나의 선택을 저장해나간다.

이 때 규칙이 필요한데 이것이 점화식이다.

 

이 문제에서는 3잔을 연속해서 선택할 수 없다.

네번 째 잔을 선택했을 때를 생각해보자.

 

선택할 수 있는 경우의 수는

1. 첫 번째 잔 + 세 번째잔 + 네 번째 잔 - 바로 이전 잔을 선택한 경우

2. 두 번째 잔 + 네 번째 잔 - 바로 이전 잔을 스킵한 경우

이다.

 

만약 이전 잔을 마셨다면 현재 잔의 앞앞 잔, 즉 n - 2 번째 잔은 선택하지 못한다.

그러나 이전 잔을 스킵했다면 n - 2번째 잔을 선택할 수 있다.

 

첫 번째 잔부터 뒤로 가면서 둘 중에 더 큰 값을 선택하여 더한다.

d[1] = data[1]이다.

첫 번째는 무조건 첫 번째이다.

 

두 번째는 d[2] = data[1] + data[2]이다.

d[2]는 선택할 수 있는 것이 앞에 하나밖에 없다. 무조건 선택하는 것이다.

 

세 번째부터 점화식을 이용한다.

d[n] = max(d[n - 3] + data[n - 1] + data[n], d[n - 2] + data[n])

말로 풀어서 설명하면

현재 잔은

앞 잔 + 앞앞앞 잔 or 앞앞 잔

중에서 더 큰 것을 선택하면 된다.

 

그러나 현재 생각하지 않은 경우가 있다.

바로 두 번 선택하지 않는 경우이다.

 

data = [100, 400, 2, 1, 4, 200] 일 때

실제 정답은 100 + 400 + 4 + 200 = 704이다.

 

그러나 위의 점화식만 적용한다면 1을 선택하여 701이 결과로 나온다.

두 번 연속으로 선택하지 않는 경우가 존재하는 것이다.

 

더 큰값을 저장한 이후에 이 값이 바로 전 값보다 큰 지 항상 확인을 해야 한다.

내가 지금 위의 두 가지 중에 더 큰 값을 정하고 합했어도 만약 이전의 값이 더 크다면

둘 다 선택하지 않고 바로 이전 값을 그대로 유지하는 것이다.

 

[소스 코드]

n = int(input())

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

d = [0] * (n + 1)

d[1] = data[1]
if n > 1:
    d[2] = data[1] + data[2]

if n > 2:
    for i in range(3, n + 1):
        d[i] = max(d[i - 2] + data[i], d[i - 3] + data[i - 1] + data[i])
        d[i] = max(d[i - 1], d[i])

print(d[n])