알고리즘
백준 파이썬 2156번 포도주 시식
chaewonni
2024. 1. 19. 22:04
🚀접근하기
<다이나믹 프로그래밍>
지금까지 풀었던 문제들을 토대로 케이스를 나누고, '지금 나'를 기준으로(반복문에서 지금의 i) 풀자는 생각을 갖고 풀었다.
케이스를 나눠가며
1) # i-2번째 포도주 마시고 i-1번째 포도주 마심 X O X
# i-2번째 포도주 안마시고 i-1번째 포도주 마심 X O O
2)# i-2번째 포도주 안마시고 i-1번째 포도주 마심 X O O
3)# i-2번째 포도수 마시고 i-1번째 포도주 안마심 O X O
이렇게 3가지의 경우를 생각해 보게 되었다.
그리고 나서 신기하게 i가 늘어날수록 저 노란색 화살표의 순서대로 계속해서 가는 규칙이 보였다....! (0 -> 2 -> 1 -> 0 -> 2 -> 1 .....)
🎉코드
n = int(input())
s_list=[]
for _ in range(n):
s_list.append(int(input()))
dp=[[0]*3 for _ in range(n)]
for i in range(0,n):
if i==0:
dp[i][0] = s_list[0]
dp[i][1] = 0
dp[i][2] = s_list[0]
elif i==1:
dp[i][0] = s_list[0]
dp[i][1] = s_list[0] + s_list[1]
dp[i][2] = s_list[1]
else:
# i-2번째 포도주 마시고 i-1번째 포도주 마심 X O X
# i-2번째 포도주 안마시고 i-1번째 포도주 마심 X O O
dp[i][0] = max(dp[i-1])
# i-2번째 포도주 안마시고 i-1번째 포도주 마심 X O O
dp[i][1] = dp[i-1][2] + s_list[i]
# i-2번째 포도수 마시고 i-1번째 포도주 안마심 O X O
dp[i][2] = dp[i-1][0] + s_list[i]
print(max(dp[n-1]))
n이 1개일 때랑 (i==0) 2개일 때는 (i==1) 따로 나누어 작성해주었고, 3개 이상일 때부터 dp를 적용시켜 주었다.
💪다짐
푸는 시간이 오래 걸리긴 했지만,, 그래도 막상 풀고나니 뿌듯했다.. 이제서야 뭔가 진짜 dp를 이해한듯한 느낌이 들었다.
풀수록 재미있는 알고리즘이 dp인 것 같다!