2156 포도주 시식
by 브이담곰https://www.acmicpc.net/problem/2156
✔ 유형 : DP
✔ 문제 풀이:
점화식을 세우는 접근방식은 다음과 같다
1. 맨 마지막 포도주를 무조건 선택한다 했을 때, 연속 두개를 선택하고 싶다면,
arr[i] ( 마지막 포도주 ) , arr[i-1]( 마지막에서 두번째 포도주), 그리고 3개를 연속해서 선택할 수 없으므로
arr[i-2]는 선택하지 않는다.
2. 맨 마지막 포도주를 무조건 선택하고, 그 전 포도주는 선택하지 않을 때,
arr[i] ( 마지막 포도주 )를 선택하고, arr[i-1]는 선택하지 않는다.
3. 맨 마지막 포도주를 절대 선택하지 않을 때
DP[i-1] 포도주의 개수가 N-1때의 최대값을 반영하면 된다.
이를 일반화 하면
DP[i]는 세가지의 경우의 수로 일반화 하여 식을 세울 수 있다.
DP[i] = arr[i] + arr[i-1] + DP[i-3]
DP[i] = arr[i] + DP[i-2]
DP[i] = DP[i-1]
마실 수 있는 최대 포도주의 값을 구해야 하므로 세가지 경우의 수의 값 중 가장 큰 값을 반영하면 된다.
따라서,
DP[i] = max( arr[i] + arr[i-1] + DP[i-3] , rr[i] + DP[i-2] , DP[i-1] )로 점화식을 세울 수 있다.
코드
import sys input = sys.stdin.readline N = int(input()) arr = [ 0 for _ in range(N+1)] # arr도 1부터 시작 for _ in range(1,N+1): arr[_] = int(input()) DP = [ 0 for _ in range(N+1)] DP[1] = arr[1] # 초기값 예외처리 if N >= 2: DP[2] = DP[1] + arr[2] if N >= 3: for i in range(3, N+1): DP[i] = max(DP[i-1],DP[i-2] + arr[i] , DP[i-3] + arr[i] + arr[i-1]) print(DP[N])
이번 문제는 silver3 문제인 계단 오르기문제와 비슷하다고 느꼈는데, 아래 문제도 함께 생각해보면 좋을 것 같다.
블로그의 정보
농담곰담곰이의곰담농
브이담곰