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

 

백준 2156번 포도주 시식 문제 파이썬

 

 

" 💡 문제 해결 아이디어 "

 

연속으로 포도주 잔을 선택하는 문제인데 연속으로 2잔만 마실 수 있고 여러 경우 중 최선의 값을 구한다는 점에서 Dynamic Programming 알고리즘 문제라는 점을 알아낼 수 있었다.

 

 

문제 해결 방식 : 보텀업 방식

 

n : 포도주 잔의 개수

arr : 테이블 별 포도주의 양을 담는 변수

dp[i] : i번째 줄까지에서 마실 수 있는 최대 포도주 양

 

 

dp 배열 초기화

 

dp[0] = arr[0] : 2개 연속으로 마실 수 있는데 1개만 있기 때문에 arr[0] 으로 초기화

dp[1] = arr[0] : 2개 연속으로 마실 수 있는데 2개만 있기 때문에 arr[0] + arr[1] 로 초기화

dp[2] = max(arr[0] + arr[1], arr[1], arr[1]+arr[2]) : 2개 연속으로 마실 수 있는데 3개가 있기 때문에 가장 큰 경우로 초기화

 

여기서 말하는 경우는 총 3가지다.

 

현재 포도주를 안마시는 경우 ( dp[i-1] ) : o o x

현재 포도주를 마시는 경우1 ( dp[i-2] + arr[i] ) : o o x o

현재 포도주를 마시는 경우2 ( dp[i-3] + arr[i-1] + arr[i] ) : o x o o

 

 

이 중에 가장 큰 경우를 선택하여 dp에 저장하면 dp[n-1]을 출력했을 때 답을 도출할 수 있다.

 

 

그리고 dp를 초기화하는 과정에서 n > 1 일때 n > 2 일때 n > 3 일때를 나누어 값을 초기화해주어야한다.

 

나는 이 경우를 고려하지 않고 코드를 작성해서 처음에 RuntimeError(TypeError) 가 출력됐다.

 

 

RuntimeError 코드

n = int(input())
arr = [[] for _ in range(n+1)]
for i in range(0,n):
    arr[i] = int(input())

dp = [0] * n # i번째 줄까지에서 마실 수 있는 최대 포도주 양
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(dp[1], arr[0]+arr[2], arr[1]+arr[2])
for i in range(3,n):
    dp[i] = max(dp[i-1], dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i])

print(dp[n-1])

 

 

정답 코드

n = int(input())
arr = [[] for _ in range(n)]
for i in range(0,n):
    arr[i] = int(input())

dp = [0] * n # i번째 줄까지에서 마실 수 있는 최대 포도주 양 
dp[0] = arr[0]
if n > 1:
    dp[1] = arr[0] + arr[1]
if n > 2:
    dp[2] = max(dp[1], arr[0]+arr[2], arr[1]+arr[2])
if n > 3:
    for i in range(3,n):
        # xoox의 경우 : dp[i-1]
        # ooxo의 경우 : dp[i-2]+arr[i]
        # oxoo의 경우 : dp[i-3]+arr[i-1]+arr[i]
        dp[i] = max(dp[i-1], dp[i-2]+arr[i],dp[i-3]+arr[i-1]+arr[i])
print(dp[n-1])