[동적계획법, 난이도 중] 백준 2156번 포도주 시식

백준 2579번 계단 오르기와 접근법이 비슷하다.

https://kimcoder.tistory.com/54

[동적계획법, 난이도 중하] 백준 2579번 계단 오르기

이 문제에서 주어진 조건은 1가지이다.

- 연속되는 3자리의 포도주를 시식할 수 없다.

 

백준 2579번 계단 오르기 문제 조건과 차이점은 단 한 가지다.

마지막 자리를 꼭 선택할 필요가 없다는 것이다.

 

아래 사진에서 연한 노랑색은 이미 계산된 DP결과이고, 진한 노랑색은 시식할 수 있는 포도주 자리들이다.

아래 3가지 케이스중에서 가장 많은 양의 포도주를 먹을 수 있는 경우가 이 문제에서의 DP 접근법이다.

이미 계산된 DP결과 자리의 바로 다음 자리는 포도주를 시식할 수 있는 자리로 둘 수 없다.

그 이유는 연속 3자리의 포도주를 시식하게 되는 경우를 포함할 수 있기 때문이다.

이에 대해 자세한 설명은 위 백준 2579번 계단 오르기 포스팅에서 해놓았다.

 

 

 

#include <iostream>
#include <math.h>
using namespace std;
int save[10001];
int grape[10001];
int max(int a, int b) {
	if (a > b) return a;
	else return b;
}

int main() {
	int a;
	cin >> a;
	for (int i = 1; i < a + 1; i++) {
		cin >> grape[i];
	}
	save[1] = grape[1];
	save[2] = grape[1] + grape[2];
	save[3] = max(max(grape[1] + grape[3], save[2]), grape[2] + grape[3]);
	for (int i = 4; i < a + 1; i++) {
		save[i] = max(max(save[i - 3] + grape[i - 1] + grape[i], save[i - 2] + grape[i]), save[i - 1]);
	}
	cout << save[a];
}

 

 

+) 2021-10-02 백준 숏코딩 상위 0.46% 파이썬 코드

e=[0]
d=[0]
n=int(input())
for _ in range(n):e.append(int(input()))
d.append(e[1])
if n>1:d.append(e[1]+e[2])
for i in range(3,n+1):d.append(max(d[i-1],d[i-3]+e[i-1]+e[i],d[i-2]+e[i]))
print(d[n])