[기출 상] 주울 수 있는 최대 돈 1 - 동적계획법

[문제]

일렬로 놓아진 돈에 대해서, 연속으로 3개의 돈을 가질 수 없을 때 최대로 주울 수 있는 돈의 액수를 구하는 프로그램을 작성해라.

 

[풀이]

동적계획법 문제로 이전에 풀었던 포도주 시식 문제와 동일하다. 

https://stritegdc.tistory.com/44

[c++] 백준 2156 포도주 시식

 

[코드]

#include <iostream>
#include <vector>
#define max(x,y) (x>y)?x:y
using namespace std;

// 돈의개수 n과 크기가 n인 수열 M이 주어졌을 때 
// 주울 수 있는 최대 돈을 구하는 함수
int solution(int n, vector<int> M)
{
  int answer = 0;
	vector<int> m(n+1, 0);
	m[0] = M[0];
	m[1] = m[0] + M[1];
	m[2] = max(m[0]+M[2], M[1]+M[2]);
	for(int i=3; i<n; i++){
		m[i] = max(m[i-2]+M[i], m[i-3]+M[i-1]+M[i]);
		m[i] = max(m[i-1], m[i]);
	}
	answer = m[n-1];
	return answer;
}

int main() {
	int n;
	cin >> n;
	
	vector<int> M(n, 0);
	for(int i=0; i<n; i++){
       cin >> M[i];  
   }
	
	int ans=solution(n,M);
	cout << ans << endl;
	return 0;
}