백준 2156 c++ "포도주 시식" -PlusUltraCode-

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

 

 

 

 

 

 

 

[필자 사고]

동적프로그래밍 문제이다.

 

필자는 개인적으로 동적프로그래밍을 만나면 직접 손으로 풀어본다.

 

몇개의 사례를 직접 손으로 풀어봐야 점화식이 만들기가 쉬워진다.

 

이 문제를 손으로 푼 결과  특정 인덱스에 해당하는 값의 최대값을 구하기 위해서는

 

1. 3칸 전Dp + Arr[i-1] + Arr[i]인 경우

2. 2칸전 Dp + Arr[i]

3. 1칸전 Dp[i-1] 인 3가지 경우중 최대값을 갱신해주면 풀 수 있게 된다.

 

Dp[i] = max(Dp[i-3]+  Arr[i-1] + Arr[i] , Dp[i-2] + Arr[i] , Dp[i-1]);

 

1번 해설 :

현재 idx와 이전 idx를 선택하게되면 연속으로 전전idx를 선택 못하게 된다 따라서 Dp전전전을 고르면 된다.

 

2번 해설

현재 idx를 선택하고 이전 idx를 선택 하지 않고 dp전전을 고르면 된다.

 

3번 해설

현재 idx를 선택하지 않고 이전 dp를 선택하면 된다.

 

[필자 코드]

#include<iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int n;
int Result = 0;
vector<int> arr;
vector<int> Dp;


void Input() {

	cin >> n;

	arr.resize(n);
	Dp.resize(n + 1);

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
}

int getMax(int a, int b, int c) {

	int maxNum = max(a, b);
	return max(c, maxNum);
}

void Solve() {

	Dp[0] = arr[0];
	Dp[1] = arr[0] + arr[1];
	Dp[2] = getMax(arr[0] + arr[1], arr[0] + arr[2], arr[1] + arr[2]);
	Result = getMax(Dp[0], Dp[1], Dp[2]);
	for (int i = 3; i < arr.size(); i++) {
		Dp[i] = getMax(Dp[i - 3] + arr[i - 1] + arr[i], Dp[i - 2] + arr[i], Dp[i - 1]);
		Result = max(Dp[i], Result);
	}

	cout << Result;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	Input();
	Solve();
}