2020. 2. 1. 17:38ㆍAlgorithm/문제풀이
dp 백준 2156 포도주 시식
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고
www.acmicpc.net
포도주 시식은 유명한 dp문제이다. 풀어본 느낌상 이전의 계단 오르기와 매우 비슷한 문제였다.
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩
www.acmicpc.net
그렇지만 몇가지 차이점이 있다.
계단오르기 문제는 위로 올라가기 위해 무조건 밟아야한다. 반면 포도주는 그 포도잔을 마시거나 안마시거나 선택할 수 있다. 그래서 지금 마시는 잔이 최고가 아니면 무시해도 된다. 공통점으로는 연속 세개를 이용못한 다는 점이다. 그래서 점화식이 계단 오르기와 같이 나온다. 단지 저 마시지 않는 경우만 잘 생각하여 점화식을 추가해주면 된다.
그리고 차이점인 현재의 포도주 잔을 마시거나 안마시거나를 이전 dp와 비교하여 현재 dp의 값을 구할 수 있다.
dp[i] = max(arr[i-1] + dp[i-3], dp[i-2]) + arr[i];
dp[i] = max(dp[i-1], dp[i]);#include <cstdio>
#include <algorithm>
long long arr[10002];
long long dp[10002];
using namespace std;
int main(){
int N;
scanf("%d", &N);
for(int i = 1; i <= N; i++)
scanf("%lld", &arr[i]);
dp[1] = arr[1];
dp[2] = arr[2] + arr[1];
for(int i = 3; i <= N; i++){
dp[i] = max(arr[i-1] + dp[i-3], dp[i-2]) + arr[i];
dp[i] = max(dp[i-1], dp[i]);
}
printf("%lld", *max_element(dp, dp+N+1));
}'Algorithm > 문제풀이' 카테고리의 다른 글
| dp 백준 9251 LCS (0) | 2020.02.02 |
|---|---|
| dp 백준 11053, 11054 가장 긴 증가하는 부분 수열 (0) | 2020.02.01 |
| dp 백준 쉬운 계단 수 10844 (0) | 2020.02.01 |
| dp 백준 1463 1로 만들기 (0) | 2020.01.31 |
| dp 백준 2579 계단 오르기 (0) | 2020.01.30 |