[백준] 2156 - 포도주 시식(Dynamic programming) - (python 파이썬)

문제 링크 : https://pacific-ocean.tistory.com/152

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

 

풀이과정 :

3연속을 제외해야하는것 때문에 점화식을 도출해 내기가 쉽지않았다.

몇번의 생각 결과,

dp[i] = dp[i-3] + glasses[i-1]+[glasses[i]  or dp[i-2] + glasses[i] or dp[i-1] 중에서

최대값을 찾아야한다는것이 핵심이다.

 

glass_num = int(input()) # 총 포도잔의 수
glasses = [0] #n번 포도잔에 담긴 포도주의 양
for i in range(glass_num):
    glasses.append(int(input()))
dp = [0, glasses[1]]
if glass_num > 1:
    dp.append(glasses[1] + glasses[2])
for i in range(3, glass_num+1):
    dp.append(max(dp[i-3]+glasses[i-1]+glasses[i], dp[i-2]+glasses[i], dp[i-1]))
print(dp[glass_num])

 

풀이과정 :

동적프로그래밍이다 라고 생각을 안하고 풀었을때 이렇게 점화식을 세워서 유추해낼 수 있을지

걱정이다.