[백준] 2156번 포도주 시식 (Python)

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

2156번: 포도주 시식

---

풀이과정

①문제 바라보기

DP문제임은 자명하다. 계단 오르기 문제랑 굉장히 유사하게 느껴졌다.

이것이 계단오르기다.

https://stopmin.tistory.com/42

[백준] 2579번 계단오르기 (Python)

이 문제의 조건은 두가지다.

1. 잔을 선택하면 다 마셔야한다. 그리고 마시고 원래 위치에 둬야한다.
2. 연속으로 세 잔은 못마신다.

②아이디어 펼치기

두 번 연달아 마시지 않는 경우를 고려하지 않은 코드

일단 grape list와 dp list를 따로 만들었다. 하나만 만들 경우에 나중에 문제가 생기기 때문이다. (만약 선택한 길이 맞지 않은 경우 난처해집니다.)

그리고 하던대로 for문을 돌려서 dp[i]  = max(dp[i-2]+grape[i],dp[i-3]+grape[i-1]+grape[i])를 사용했는데 아주 충격적이게도 6퍼센트에서 틀렸다고 나왔다.

굉장히 속상하지만 이유를 찾는다.

 

굉장히 충격적인 사실을 알게됐다.. 이 문제는 계단오르기 문제랑 굉장히 달랐다. 1번째 잔을 마시고 바로 4번째 잔을 마셔도 된다.. 그러니 input이 7/100/100/10/10/100/100/10일 경우 답이 400이 나와야하는데 320이 나옴.

그러니 dp[i] = i에서 가장 큰 값.. 식으로만 풀면 틀리게 된다.

 

근데 또다른 사실을 알게 되었다. 2번 연달아 마시지 않는 경우만 더해주면 된다는 사실이다. 그렇다면 아래의 점화식만 추가적으로 써주면 된다.

dp[i] = max(dp[i-1], dp[i])

 

③최종코드

N = int(input())
grape = [0]

for _ in range(N):
    grape.append(int(input()))

if N == 1:
    print(grape[1])
else:
    dp = [0]*(N+1)
    dp[0] = grape[0]
    dp[1] = grape[0] + grape[1]
    dp[2] = max(grape[0] + grape[2], grape[1] + grape[2])
    for i in range(3,N+1):
        dp[i] = max(dp[i-2] + grape[i],dp[i-3] + grape[i-1] + grape[i])
        dp[i] = max(dp[i-1], dp[i])
    print(max(dp))

---

후기

내가 모두 안다고 생각하지 말자..

그리고 나아가던 방법이 안된다고 포기하지 말자..

코드 한 줄만 추가하면 되는데 엎을 생각 하니깐 40분을 썼데이