🚀접근하기

<다이나믹 프로그래밍>

지금까지 풀었던 문제들을 토대로 케이스를 나누고, '지금 나'를 기준으로(반복문에서 지금의 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인 것 같다!