Algorithm/BaekJoon

백준 22.02.17. 2156번 - 포도주 시식

HappyFrog 2022. 2. 17. 00:57

n = int(input())

wine = [0]

for i in range(n):
    wine.append(int(input()))

dp = [0 for i in range(10001)]
dp[1] = wine[1]

for i in range(2, n+1):
    if i == 2:
        dp[2] = wine[1] + wine[2]
    else:
        dp[i] = max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i])
print(dp[n])
  • wine과 dp리스트의 0인덱스는 0으로 만들어두었습니다.
    • wine[1] = 1번째 와인잔, dp[1] = 1번째 와인잔까지의 최대 와인량을 표현하는 데 있어서 조금 더 알아보기 쉽도록 작성하기위해서 입니다.
  • wine리스트에 입력받은 와인량을 모두 추가해줍니다.
  • i번째까지의 최대 와인량을 저장할 dp리스트는 0~10000인덱스까지 미리 생성했습니다.
  • 그리고 규칙을 시작하기 위해서 dp[1] = wine[1]로 미리 설정해주었습니다.
    • 이것은 반복문 내의 조건문으로 분기를 나누어도 됩니다.
  • 반복문 내에서 dp[2]는 규칙없이 1번째와 2번째 와인량의 합과 같기때문에 분기를 나누어 지정해주었습니다.
    • 이 역시 반복문 바깥에서 따로 작성해주어도 됩니다.
  • 그리고 dp[i]의 최대량을 구하기위한 접근방법은 세가지  있습니다.
    1. dp[i-1]까지의 최댓값을 취하고 wine[i]는 건너뛰는 방법
    2. dp[i-2]까지의 최댓값을 취하고 wine[i-1]은 건너뛴 뒤 wine[i]를 더하는 방법
    3. dp[i-3]까지의 최댓값을 취하고 wine[i-2]는 건너뛴 뒤 wine[i-1], wine[i]를 더하는 방법
  • 이 세가지 경우의 수를 모두 비교하여 최댓값을 dp[i]에 저장합니다.
  • 마지막으로 dp[n]을 출력해주면됩니다.