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

문제 출처:

www.acmicpc.net/problem/2156

2156번: 포도주 시식

문제 풀이:

• 문제의 조건이 연속하는 3잔을 마실 수 없다는 것이다.
• 이에 대해서 i번째 포도주에 대한 포지션을 다음과 같이 생각할 수 있다.
  • i 번째 포도주 앞에 1잔 먹고 i번째 포도주 먹는 경우 : A (n-2번째 잔은 마실 수 없다)
  • i번째 포도주 바로 앞에는 안먹고 그전꺼 1잔 먹고 i번째 먹는경우 : B (n-1번째 잔은 마실 수 없다)
  • i번째 포도주 안먹고 앞에서 연속 2잔 먹는경우 : C (n번째 잔을 마실수없다)
• 이렇게 표현하면
  A의 경우 : wine[n] + wine[n-1] + dp[n-3]
  B의 경우 : wine[n] + dp[n-2]
  C의 경우 : dp[n-1]
• 이중에 가장 큰값을 가져가면서 갱신해주면된다.
• 필자는 로직은 금방 생각햇는데 초기값과 index 조절을 잘못해줘서 몇번 틀렸다.

n = int(input())
wines =[]

for _ in range(n):
    wines.append(int(input()))

if n==1:
    print(wines[0])
elif n==2:
    print(wines[0]+wines[1])
else:
    dp=[0]*(n+1)
    dp[0]=wines[0]
    dp[1]=wines[0]+wines[1]
    dp[2]=max(dp[1],wines[1]+wines[2],wines[0]+wines[2])

    for i in range(3,n):
        dp[i]=max(dp[i-1],dp[i-2]+wines[i],wines[i]+wines[i-1]+dp[i-3])

    print(dp[n-1])