백준 2156 - 포도주 시식

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

2156번: 포도주 시식

 

 

드디어 구글링을 하지 않고 DP문제를 풀어내었다 ㅎㅅㅎ

 

근데 다른 사람들의 코드와 비교해보았을 때, 내 코드는 시간이 좀 더 걸리는 편이라.. 다른 사람의 코드를 공부해보기 위한 포스팅을 작성해보도록 하겠다. 이왕하는 김에 내 코드도 같이 리뷰해보려고 한다.

 

이 문제를 보자마자 백준 2579번- 계단 오르기와 굉장히 유사한 문제라고 생각했다.

결국 숫자들을 연속적으로 합하여 최고 점수를 산출해야되는데, 연속적으로 3개의 숫자는 더해질 수 없다는 조건이 동일한 대신 건너뛸 수 있는 조건이 달랐다. 계단 오르기는 최대 한 칸만 건너 뛸 수 있는데, 포도주 시식은 건너 뛰는 것에 대한 제약사항이 없다.

 

나는 이 문제를 읽고 다음과 같은 알고리즘으로 코드 구현에 성공하였다.

1. dp에는 i번째 포도주까지의 최대합이 들어있는 리스트이다.

2.  i번째 포도주는 마실수도, 안마실 수도 있기 때문에 해당 포도주까지의 최대합을 해당 포도주를 마셨을 경우와 마시지 않았을 경우로 나누어 최대합을 구하고자 했다.

dp[i][0] => i번째 포도주를 마시지 않았을 경우 i번째 포도주까지의 최대합

dp[i][1] => 마셨을 경우  i번째 포도주까지의 최대합

 

3. i번째 포도주를 마셨을 경우의 최대합

=> 두 가지 경우가 있다.

3-1. 전전 포도주를 마시고, 전 포도주는 마시지 않고, i번째 포도주를 마실 경우

dp[i-2][1] : 전전 포도주를 마셨을 경우의 최대합

3-2. 전전 포도주를 마시지 않고, 전 포도주는 마시고, i번째 포도주를 마실 경우

dp[i-2][0] + grape[i-2] : 전전 포도주를 마시지 않았을 때의 최대합 + 전 포도주를 마셨을 경우

*주의할 점*

여기서 dp[i-2][0] + grape[i-2] 이렇게 쓰지 않고

dp[i-1][1] : 전 포도주를 마셨을 경우, 전 포도주까지의 최대합

이렇게만 쓴다면, 어차피 i번째 포도주는 마시는게 확정인데 dp[i-1][1] 이 케이스에는 전전 포도주와 전 포도주를 모두 마셨을 경우가 포함될 수 있으니 i번째 포도주까지 마시게 된다면, 연속적으로 3잔을 마시게 되어 이 문제의 조건에 어긋난다. 따라서, 반드시 dp[i-2][0] + grape[i-2] 이렇게 써야한다.

i번째 포도주를 마셨을 경우의 최대합만 구하면 되므로, 두 경우에서 max만 가져와서 저장하면 된다.

 

4. i번째 포도주를 마시지 않았을 경우의 최대합

=> 마찬가지로 두 가지 경우가 있다.

4-1. 전 포도주를 마시고, i번째 포도주를 마시지 않을 경우

dp[i-1][1]

4-2. 전 포도주를 마시지 않고, i번째 포도주를 마시지 않을 경우

dp[i-1][0]

i번째 포도주를 마시지 않았을 경우의 최대합만 구하면 되므로, 두 경우에서 max만 가져와서 저장하면 된다.

 

위의 1~4를 구현한 코드는 다음과 같다.

내 코드)

n = int(input())
dp = [[0] * 2 for i in range(n+1)]
grape = []

for i in range(n):
    grape.append(int(input()))

if n>2:
    dp[0][0] = 0  # 안먹음
    dp[0][1] = 0  # 먹음
    dp[1][0] = 0
    dp[1][1] = grape[0]
    dp[2][0] = grape[0]
    dp[2][1] = grape[0] + grape[1]

    for i in range(3, n+1):
        dp[i][1] = max(dp[i-2][1], dp[i-2][0] + grape[i-2]) + grape[i-1]
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])

    print(max(dp[n]))
else:
    print(sum(grape))

계단 오르기와 마찬가지로 n이 3보다 작으면 최대합은 모든 수를 더해서 출력하면 되므로, 조건문을 밖에 걸었다.

 

 

이제 다른 풀이 코드를 리뷰해보도록 하겠다.

다른 풀이 코드)

n = int(input())
w = [0]
for i in range(n):
    w.append(int(input()))
dp = [0]
dp.append(w[1])
if n > 1:
    dp.append(w[1] + w[2])
for i in range(3, n + 1):
    dp.append(max(dp[i - 1], dp[i - 3] + w[i - 1] + w[i], dp[i - 2] + w[i]))
print(dp[n])

 

위 풀이 코드는 아래 포스팅을 참고

https://pacific-ocean.tistory.com/152

[백준] 2156번(python 파이썬)