[BOJ] 2156: 포도주 시식 (Python)

문제 링크

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

풀이 전략

Dynamic Programming

아래 세 가지 경우 중 최대를 구하는 동적계획법을 세우면 답을 구할 수 있다.

1. $i$ 번째 순서의 포도주를 마시는 경우

   1-1. $i-1$번째 순서에서 포도주를 먹는 경우

   • dp[i] = dp[i-3] + wine[i-1] + wine[i]
     

   1-2. $i-1$번째 순서에서 포도주를 먹지 않는 경우

   • dp[i] = dp[i-2] + wine[i]

2. $i$번째 순서의 포도주를 마시지 않는 경우

• dp[i] = dp[i-1]

구현

if __name__ == "__main__":
    n = int(input())
    # 0번째 값은 0으로 초기화
    wine = [0]
    for _ in range(n):
        wine.append(int(input()))
    # 0번째 값은 0으로 초기화
    dp = [0]
    
    # 첫 번재 값 초기화
    dp.append(wine[1])
    
    if n>1:
    	# 두 번째 값 초기화
        dp.append(wine[1] + wine[2])
        
        # 세 번째 값부터 규칙 적용
        for i in range(3, n+1):
            dp.append(max(dp[i-1], dp[i-3]+wine[i-1]+wine[i], dp[i-2]+wine[i]))
    print(dp[n])

복잡도

• Basic Operator: max
• Time Complexity: $O(n)$

삽질

if __name__ == "__main__":
    n = int(input())
    wine = []
    for _ in range(n):
        wine.append(int(input()))
    dp = [0] * (n+1)
    
   
    if n <= 3:
        if n == 1: print(wine[n-1])
        if n == 2: print(wine[n-2]+wine[n-1])
        if n == 3: print(max(wine[n-2]+wine[n-1], wine[n-3]+wine[n-1]))

    else:
        dp[0] = wine[0]+wine[2]
        dp[1] = wine[0]+wine[1]
        dp[2] = wine[1]+wine[2]
        
        for i in range(3, n, 3):
            if i+2 >= n: pass
            else: dp[i] = dp[i-3] + wine[i] + wine[i+2]

            if i+1 >= n: pass
            else: dp[i+1] = dp[i-2] + wine[i] + wine[i+1]

            if i+2 >= n: pass
            else: dp[i+2] = dp[i-1] + wine[i+1] + wine[i+2]

        print(max(dp[n-2], dp[n-1], dp[n]))