[백준/Python] - 2156 포도주 시식

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

 

제출코드

N = int(input())
dp = [0] * (N+1)
N_list = [0]
for _ in range(N):
    N_list.append(int(input()))
dp[1] = N_list[1]
if N > 1:
    dp[2] = N_list[1] + N_list[2]
for i in range(3,N+1):
    dp[i] = max(dp[i-1], dp[i-2] + N_list[i] , N_list[i-1] + N_list[i] + dp[i-3])
print(max(dp))

 

일단 dp를 0으로 초기화해줬다. dp[0]에도 0을 추가해줘서 dp인덱스와 N_list의 인덱스를 맞춰줬다.

아래 그림으로 점화식을 도출해보면

dp[1]과 dp[2]는 점화식이 따로 필요없이 확정이 되는 값이다 

dp[3]부터는 최대값을 고르는 방법이

1. dp[0] + N_list[3]
2. dp[2]
3. dp[1] + N_list[3]

이렇게 3가지로 식을 세우면 연속3잔을 마시지 않는 조건을 만족한다.

 

 

 

인덱스 에러 코드

N = int(input())
dp = [0] * (N+1)
N_list = [0]
for _ in range(N):
    N_list.append(int(input()))
dp[1] = N_list[1]
dp[2] = N_list[1] + N_list[2]
for i in range(3,N+1):
    dp[i] = max(dp[i-1], dp[i-2] + N_list[i] , N_list[i-1] + N_list[i] + dp[i-3])
print(dp[N])

맨처음에 코드를 짤 때는 아무런 조건을 주지 않고 코드를 작성하다보니

N이 1일때 값 처리를 따로 하지 않아서 인덱스 에러가 났다.

N이 1일때는 dp[2]의 값이 없기때문에 N > 1보다 크다는 값을 따로 정해줘야한다.

 

그래서 N이 1보다 클때 다음과 같은 조건을 주었다.

if N > 1:
    dp[2] = N_list[1] + N_list[2]