BOJ 18185, 18186 | 라면 사기

BOJ 18185 라면 사기 (Small)
BOJ 18186 라면 사기 (Large)

HI-ARC 디코방에서 누가 하루종일 푸셨다고 해서 찾아보게 되었다.

처음 볼 때 그리디인가? 싶었고 알고리즘 분류 보고 확신했다.

사실 DP인가 그리디인가 헷갈려서 좀 고민하긴 했다.

라면 3개 구매 시 개당 7/3원이고,

라면 2개 구매 시 개당 5/2원,

라면 1개 구매시 개당 3원이다.

명백하게 3개 > 2개 > 1개 순으로 효율이 좋다.

따라서 최대한 연속으로 구매할수록 좋다.

p1을 i-1에서 낱개 구매한 것,
p2를 i-1과 i-2에서 2개 구매한 것으로 두자.

그러면 i에서는 p1과 합쳐서 낱개를 2개로 만들고,
p2와 합쳐 2개를 3개로 만든다.

그러나 2개 번들이 3개 번들이 될 때는 개당 가격이 93.333...%가 되고,
1개 번들이 2개가 될 때는 개당 가격이 83.333...%가 되어 2=>3 보다는 1=>2가 더 이득이다.

따라서 낱개를 2개 번들로 먼저 교환해야 하고, 그 다음에 2개 번들을 3개 번들로 교환해야 한다.

따라서 p1이 먼저 i번에 있는 라면과 합쳐져서 p2(새로운 2개 번들)와 p1_old(남은 1개)로 나뉘고,
그 다음에 p2가 남은 i번 라면과 합쳐져 p3(3개 번들)와 p2_old(남은 2개 번들) 로 나뉜다.

이때 p1, p2_old, p3만 sum에 더해주면 된다.

이 연산에서 합쳐진 p1은 p2로 밀려나고, 연산이 끝나고 남은 i번째 라면이 p1이 되며,
합성되지 못한 p1_old와 p2_old, 그리고 3개가 된 p3는 연산이 끝나 sum에 각각 (B, B+C, B+2C)를 곱해 더해지게 되는 것이다.

.
만약 2개 번들을 3개 번들로 먼저 만들도록 했다면 다음과 같은 반례가 생긴다.
https://www.acmicpc.net/board/view/83786

//라면 사기 small
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N; cin >> N;
	vector<int> price;
	
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		price.push_back(t);
	}
	
	int p1 = 0, p2 = 0;
	int sum = 0;
	//p1 i-1 purchase 1
	//p2 i-1 i-2 purchase 2
	
	for (int i = 0; i < N; i++){
		int p = price[i];
		
		int pp1 = min(p, p1); // i, i-1
		p -= pp1; p1 -= pp1;
		
		int pp2 = min(p, p2); // i, i-1, i-2
		p -= pp2; p2 -= pp2;
		
		sum += p1*3;
		sum += p2*5;
		sum += pp2*7;
		
		p2 = pp1;
		p1 = p;
		
	}
	sum += p1*3;
	sum += p2*5;
	
	cout << sum;
	
}

//라면 사기 Large
#include <bits/stdc++.h>
using namespace std;

#define lint long long

int main(){
	lint N; cin >> N;
	lint B, C; cin >> B >> C;
	vector<int> price;
	
	if ( B < C ) C = B;
	
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		price.push_back(t);
	}
	
	lint p1 = 0, p2 = 0;
	lint sum = 0;
	//p1 i-1 purchase 1
	//p2 i-1 i-2 purchase 2
	
	for (int i = 0; i < N; i++){
		lint p = price[i];
		
		lint pp1 = min(p, p1); // i, i-1
		p -= pp1; p1 -= pp1;
		
		lint pp2 = min(p, p2); // i, i-1, i-2
		p -= pp2; p2 -= pp2;
		
		sum += p1*B;
		sum += p2*(B+C);
		sum += pp2*(B+2*C);
		
		p2 = pp1;
		p1 = p;
		
	}
	sum += p1*B;
	sum += p2*(B+C);
	
	cout << sum;
	
}