백준 온라인저지 2156번 포도주 시식
문제풀러 바로가기👇👇👇👇👇👇
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
문제풀이
다이나믹 프로그래밍을 이용해 문제를 풀 수 있다. 연속으로 3잔을 마실 수 없는 조건을 만족시켜야하고, 최대한 많은 포도주를 마셔야하기 때문에 점화식을 잘 세우고, max 메소드를 이용해야한다.
wine 맨 앞에 0인 더미 값을 넣어줘 dp와 인덱스를 맞춰줬다. 아래 코드를 통해 점화식을 도출해보자.
dp[1]와 dp[2]은 점화식이 따로 필요없이 확정되는 값이다. dp[3]부터 차례로 포도주의 최대값을 구하는 식을 만들면 공통점이 보일 것이고, 그것을 통해 점화식을 유추해낼 수 있다.
wine = [0, 6, 10, 13, 9, 8, 1]
dp = [0] * (n+1)
dp[1] = wine[1]
# n의 범위가 1이상이므로 예외 분기를 넣어야한다.
if n > 1:
dp[2] = wine[1] + wine[2]
# 점화식 도출
dp[3] = max(dp[1] + wine[3], dp[2], dp[0]+wine[2]+wine[3])
dp[4] = max(dp[2] + wine[4], dp[3], dp[1]+wine[3]+wine[4])
# 점화식은 dp[i] = max(dp[i-2]+wine[i], dp[i-1], dp[i-3]+wine[i-1]+wine[i]) 이다.이제 점화식을 바탕으로 코드를 짜면 된다.
코드
n = int(input())
wine = [0]
for i in range(n):
wine.append(int(input()))
dp = [0] * (n+1)
dp[1] = wine[1]
if n > 1:
dp[2] = wine[1] + wine[2]
for i in range(3, n+1):
dp[i] = max(dp[i-2]+wine[i], dp[i-1], dp[i-3]+wine[i-1]+wine[i])
print(dp[n])