[EPPER/13회 9번]주울 수 있는 최대 돈(상-3)

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

/*
돈을 3개 연속해서 주울 수 없다. 
그렇다면, 다음과 같이 3개의 돈이 연속으로 있다고 가정하자 

..., m, n, q,

그렇다면 일단 두가지로 나눌 수 있다.
1.n번째 돈을 주운 경우
2.n번째 돈을 줍지 않은 경우 

줍지 않은 경우에는 제약조건을 고려할 필요가 없다.
하지만 주운 경우에는 내가 이 돈을 주워서 3연속이 되지 않았는지 제약이 걸린다

이를 다시 나누면 
1-1) N번째 돈을 주움 + N-1번째 돈을 주움 (2연속)
1-2) N번째 돈을 주움 + N-2번째 돈을 주움 (연속x)
두가지 경우만 가능하다 

그렇다면 N번째 돈 앞에 서있을 때 취할 수 있는 상황은 3가지이다.
1. 돈을 줍지 않기 (non update) -> 이전 최대 값과 같음(n-1번쨰 까지의 최댓값)  
2. N-1번째 돈과 N번째 돈을 줍기 (update) -> n-3까지의 최대값 + n-1번째 돈 + n번째 돈
3. N-2번째 돈과 N번째 돈을 줍기 (update) -> n-2까지의 최대값 + n번째 돈 

3가지 상황중 최댓값을 고르면된다. 

2,3번은 업데이트되는 값이고, 1번을 고른다면 지금까지 가지고있는 돈에서 업데이트가 되지 않을 것이다.
값이 업데이트될 수 있으며, 이들중에 비교를 해야한다는 말은
N번째 돈에 도달할 때 마다 해당 상황에 해당하는 최대 값을 어딘가에 저장해야한다는 의미이고
보통 그런경우 배열을 사용하여 arr[N]에 N번째 동전을 맞이한 상황에서 최대값을 저장할 것이다.

ㄱㄱ!


*/


vector<int> moneyBag;

int solution(vector<int> moneyList, int n){
	int result=0;
	// 구상한 알고리즘은 n-1,n-2인덱스가 존재할 때부터 유효하기 때문에 index 0, 1에 대해서는 미리 채워주어야함
	moneyBag.push_back(moneyList[0]);
	moneyBag.push_back(moneyList[0]+moneyList[1]);
	//moneyBag[0]=moneyList[0];
	//moneyBag[1]=moneyBag[0] + moneyList[1];
	
	for(int i=2; i<n; i++){
		result = max({moneyBag[i-1],moneyBag[i-3]+moneyList[i-1]+moneyList[i],moneyBag[i-2]+moneyList[i]});
		//cout<<result;
		moneyBag.push_back(result);
	
		}
	
	result=moneyBag[n-1];
	return result;
}

int main() {
	int n;
	cin >> n;
	
	vector<int> moneyList;
	int money;
	
	for(int i=0;i<n;i++){
		cin >> money;
		moneyList.push_back(money);
	}
	
	
	cout << solution(moneyList,n) << endl;
	return 0;
}

 

 

최대 / 최소 3개 이상의 매개변수 쓸 경우

#include <algorithm>

 

max({a,b,c,});

min({a,b,c});