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]의 최대량을 구하기위한 접근방법은 세가지 있습니다.
- dp[i-1]까지의 최댓값을 취하고 wine[i]는 건너뛰는 방법
- dp[i-2]까지의 최댓값을 취하고 wine[i-1]은 건너뛴 뒤 wine[i]를 더하는 방법
- dp[i-3]까지의 최댓값을 취하고 wine[i-2]는 건너뛴 뒤 wine[i-1], wine[i]를 더하는 방법
- 이 세가지 경우의 수를 모두 비교하여 최댓값을 dp[i]에 저장합니다.
- 마지막으로 dp[n]을 출력해주면됩니다.