[백준/파이썬] 2156 : 포도주 시식

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

2156번: 포도주 시식

문제 요약 : 포도주 잔이 일렬로 놓여있다. 포도주를 연속해서 3잔 마실 수 없을 때, 가장 많은 양의 포도주를 마시는 방법을 구하라.

 

시도 1 )

앞서 풀었던 계단 오르기와 유사하다 생각하여 거의 똑같이 풀었다.

사실 풀면서도 분명 계단오르기는 도착점이 정해져있고, 이건 도착점이 정해져 있지 않기 때문에 차이점이 있을 거라고 생각했지만 어디를 어떻게 차이를 둬야할 지 감이 오지 않아 일단 풀어보기로 했다.

 

 

일단 dp[i]는 i잔을 마실 때에, 가장 큰 값을 저장해주었다. 도착점이 정해져 있지 않았기에, ans를 따로 만들어 dp를 돌때마다 ans에 max값을 해서 가장 큰값을 계속 업데이트 시켜줬다.

n = int(input())
podo = [0]
dp = [0] *(n+1)
ans = 0

for i in range(1,n+1):
    podo.append(int(input()))
    if i == 1:
        dp[1] = podo[1]
    elif i == 2:
        dp[2] = podo[1] + podo[2]
    else:
        dp[i] = max(podo[i] + podo[i-1] + dp[i-3] , podo[i] + dp[i-2])
    ans = max(ans,dp[i])

print(ans)

 

틀렸습니다..ㅎ..

틀린이유를 이해 못해서 반례를 엄청 찾고 다녔다.

 

반례는

입력값이

7

10

100

100

10

10

100

100

일 경우이다.

 

이때 저 위의 코드로 돌리게 되면

dp가 [0, 10, 110, 200, 120, 210, 310, 320]이 나오게 되면서 최대값이 320으로 출력된다.

그러나, 그냥 눈으로만 봐도 100 100 100 100 이렇게 네잔을 마시는 400이 더 큰것을 알 수 있다.

 

올바르게 풀었을 경우에는 [0, 10, 110, 200, 200, 210, 310, 400]이 나와야한다는 것이다... 즉, 10을 안먹었을 때가 더 클 수 있다. dp[i]에 해당 음료를 먹었을 경우의 가장 큰 값이 들어가기 때문에 일어나버린일.... 안먹을 수도 있음을 간과했다.

 

만일, 위의 코드로 푼다면 i,i-1,i-3 (100,100,dp(10))음료를 먹을경우, i,i-2 (100,dp(10))음료를 먹을 경우만 해당이 된다. 그러나 i,i-1,i-4를 먹을 경우는 알 수 없다는 것임......(100,100,dp(100))

이게 도착점이 정해져있고 안정해져있고의 차이였던 것 같다..🙄

 

 

자세한건 

https://www.acmicpc.net/board/view/60664

글 읽기 - 잘 이해가 되지 않아 이렇게 질문드립니다..ㅜㅜㅜ

이 질문의 해답을 읽으면 이해할 수 있다.😇😇😇

 

시도 2 )

n = int(input())
podo = [0]
dp = [0] *(n+1)

for i in range(1,n+1):
    podo.append(int(input()))
    if i == 1:
        dp[1] = podo[1]
    elif i == 2:
        dp[2] = podo[1] + podo[2]
    else:
        dp[i] = max(podo[i] + podo[i-1] + dp[i-3] , podo[i] + dp[i-2], dp[i-1])

print(dp[n])

dp[i]값에 언제나 가장 큰 값이 들어간다는 것을 알고나면 굳이 ans를 통해 최대값을 구해줄 필요없이 가장 마지막 값을 불러오면 된다.