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

 

문제 링크

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

 

 

 

 

TIL

• DP는 "현재 최적의 선택은 이전 최적의 선택으로부터 만들어진다"는 원칙 아래 동작함.
• 그래서 모든 가능한 상태 중 "조건을 만족하는 최댓값만 저장"하면, 그 다음 상태를 만들 때 조건 위반 없이 옳은 해를 누적해갈 수 있음
  • 나는 문제에서 "확실하지 않은 경우(?)는 무시해도 되는가?"에 대해서 고민함
  • 예를 들어, dp[i-1] 이 i-1 번째에서의 최대값이니까 i-1번째를 안마셨을 수도 있음
    • 그렇게 되면 i번째는 마셔도 되는 거라고 생각함
      • 근데 그건 그거고, 앞에서부터 차례대로 계산하기 때문에 그냥 i-1 번째에 마시든 말든 신경안쓰고 (사실상 마셨다고 가정) 점화식 사용해야함
  • 확실하지 않은 경우는 안전을 위해 제외하고, 조건을 지킨 확실한 경우만 점화식에 포함해도 모든 가능한 최대 포도주 양 조합이 고려된다는 게 이 문제 DP 설계의 핵심 !! (모든 DP가 그런 거는 아님)
• IndexError 조심하기 !!!!
  
  • 주어진 범위 꼭 확인하고 점화식 사용
  • 점화식의 경우 index 에러가 발생하는 경우가 많기 때문에 꼭 작은 숫자는 따로 빼서 처리해주기
  • if-elif 사용 (if - if 말고 !!!!!)

 

 

Code

n = int(input())
wine = []
for _ in range(n):
    wine.append(int(input()))

if n == 1:
    print(wine[0])
elif n==2:
    print(wine[0]+wine[1])

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

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

    print(dp[n-1])