백준 2156 포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

 

 

EXPLANATION

 

 

문제 규칙

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

 

포도주 잔이 i개 있을 때 문제 규칙에 따라 잔들을 선택하는 경우는 i번째 잔을 기준으로 다음 3개의 경우로 나눌 수 있다.

 

1) ? ? ? ? ? X
2) ? ? ? ? X O
3) ? ? ? X O O

( ?: 선택 유무 모름, X: 비선택, O: 선택 )

• i번째 잔을 선택하지 않는 경우
• i번째 잔을 선택하는 경우, i를 포함하고 한 번 연속 하는 경우
• i번째 잔을 선택하는 경우, i를 포함하고 두 변 연속 하는 경우

 

잔 i가 가지고 있는 포도주 양을 amount[i]라 하고,

포도주 잔이 i개 있을 때 문제 규칙에 따라 잔들을 선택해서 얻을 수 있는 포도주 양의 최댓값을 dp[i]라고 하자.

 

그러면,

dp[i-1]을 이용해서 1)의 경우에 최대로 마실 수 있는 포도주 양을 구할 수 있고,

dp[i-2]와 amount[i]를 이용해서 2)의 경우에 최대로 마실 수 있는 포도주 양을 구할 수 있고,

dp[i-3], amount[i-1] 와 amount[i]를 이용해서 3)의 경우에 최대로 마실 수 있는 포도주 양을 구할 수 있다.

1. dp[i - 1]
2. dp[i - 2] + amount[i]
3. dp[i - 3] + amount[i - 1] + amount[i]

 

1), 2), 3)의 경우가 포도주 잔이 i개 있을 때 문제 규칙에 따라 잔들을 선택할 수 있는 모든 경우이므로

이 3가지 경우를 통해서 구해진 각 각의 최대로 마실 수 있는 포도주 양 중에서 가장 큰 값이 답이다.

 

 

base 구하기:

i가 1, 2 일 때 dp[i - 3]은 음의 index를 가지니 dp[1], dp[2]는 base

dp[1] = amount[1]

dp[2] = amount[1] + amount[2]

 

 

 

점화식

dp[1] = amount[1]
dp[2] = amount[1] + amount[2]

dp[i] = max(dp[i-1], max(dp[i-2] + amount[i], dp[i-3] + amount[i] + amount[i-1]))

 

 

 

얼핏보면  2579 계단 오르기 문제(풀이 보러가기)와 똑같이 3연속하지 못한다는 규칙이 있어서 두 문제가 비슷해보이지만,

재귀의 규칙이 다르다.

 

2579 문제는 i번째 계단의 값을 무조건 이용해야 해서 i -1번째를 거쳐서 i번째로 도달하는 경우와 i - 2번째를 거쳐서 i번째로 도달하는 경우 2개로 나누었다.

 

이와 달리, 이 2156 문제는 i번째 잔을 무조건 선택할 필요가 없어서, i번째 잔을 선택한 경우와 선택하지 않은 경우로 나눌 수 있었다.

 

뿐만 아니라, 2579 문제는 한 층에서 다른 층으로 움직일 때 1칸과 2칸만 갈 수 있도록 제한 되지만, 

이 2156 문제는 그런 제약이 없어서 당연히 선택된 잔 2개 사이에 비선택 잔이 얼만큼 나오는 지는 고려하지 않아도 된다.

(또 최댓값을 가지는 경우에 비선택 잔이 3개 이상 나올 수 없다. 비선택 잔이 3개가 나오면 그 중간의 잔을 선택하는 게 더 큰 값을 가지는 경우이기 때문이다.) 

 

 

 

 

이런 귀납법, 경우의 수 문제들은 경우의 수에 대해 아직 명료하게 공부하지 않았다면 혼란의 무한 루프에 빠질 수 있다.

경우를 주어진 조건을 통해 큰 기준을 가지고 나누는 것을 기억한다. 그리고 그 나눠진 경우들을 귀납법을 통해서 표현한다.

 

 

 

CODE

#include <iostream>
using namespace std;


int main(){
	int N;
	cin >> N;
	int dp[10001] = {};    //for[1, N]
	int amount[10001] = {};
	for(int i = 1; i <= N; i++) {
		cin >> amount[i];
	}
    
	dp[1] = amount[1];
	dp[2] = amount[1] + amount[2];
		
	for(int i = 3; i <= N; i++){
		dp[i] = max(dp[i-1], max(dp[i-2] + amount[i], dp[i-3] + amount[i] + amount[i-1]));
	}
	
	cout << dp[N] << " "; 

}