18185번 : 라면 사기 (Small)

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

18185번: 라면 사기 (Small)

연속된 1개 공장에서 라면을 사면 비용 3,
연속된 2개 공장에서 라면을 사면 비용 5,
연속된 3개 공장에서 라면을 사면 비용 7
의 비용을 내고 라면을 살 수 있을 때, 최소 비용을 구하는 문제였다.

아이디어 : 

접근은 dp였다. i번째까지 최적화된 배열이 있을 때 i+1번째를 최적화 시키는 방법은 뭐가 있을까?
먼저 라면을 사는 방법은 총 3가지이다.
i+1에서만 비용 3
i, i+1 에서 비용 5
i-1, i, i+1에서 비용 7
당연히 7 -> 5 -> 3 순으로 이득이고, 비용 3으로 산거 일부를 비용 5로 업그레이드, 비용 5로 산거 일부를 비용 7로 업그레이드 하는 식으로 접근했다.

만약 i+1번째와 i번째에 각각 비용 3으로 산 라면들이 있다면 그 둘 최솟값만큼 비용 5로 업그레이드 한다.

만약i번째와 i-1번째에 각각 비용 5로 산 라면들이 있고, i+1번째에 비용 5으로 업그레이드 하고 남은 라면이 있다면, 그 셋 중 최솟값만큼 비용 7로 업그레이드 한다.

그래도 i+1번째에 남은 라면들이 있다면 비용 3으로 다 살 수밖에 없다.

 

 

구현 : 

i-1번째, i번째, i+1번째에 비용 3, 5, 7로 산 라면이 몇개인지만 유지하면 되므로 dp배열은 필요 없이 그리디로 풀이 가능하다.

코드 : 

#include <bits/stdc++.h>
#define min3(a,b,c) min((a),min((b),(c)))
using namespace std;
using ll=long long int;
vector<ll> v;
struct node {
	ll a, b, c; // 비용 3, 비용 5, 비용 7
	node(ll a, ll b, ll c):a(a),b(b),c(c){}
};
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int N; cin>>N;
	for(int i=0; i<N; ++i){
		ll a; cin>>a; v.push_back(a);
	}
	ll res=3*v[0];
	
	node prev2(0,0,0); // i-1
	node prev1(v[0],0,0); // i
	for(int i=0; i<N-1; ++i){
		node prev0(0,0,0); // i+1
		// 1. prev1에서 비용 3으로 산거 일부를 prev0과 함께 비용 5로 계산한다.
		ll k=min(prev1.a, v[i+1]);
		res-=3*k;
		res+=5*k;
		prev1.a-=k;
		v[i+1]-=k;
		prev1.b+=k;
		prev0.b+=k;
		// 2. prev2와 prev1에서 비용 5로 산거 일부를 prev0과 함께 비용 7로 계산한다.
		if(i!=0){
			ll k=min3(prev2.b, prev1.b, v[i+1]);
			res-=5*k;
			res+=7*k;
			prev2.b-=k;
			prev1.b-=k;
			v[i+1]-=k;
			prev2.c+=k;
			prev1.c+=k;
			prev0.c+=k;
		}
		// 3. 남은걸 prev0에 비용 3으로 산다.
		prev0.a+=v[i+1];
		res+=3*v[i+1];
		prev2=prev1;
		prev1=prev0;
	}
	cout << res << '\n';
}