Boj 18186) 라면 사기

문제

백준 18186.

설명

출제자 블로그 에서 증명한게 있지만 난 이 방법으로 안해서 따로 기록한다.

내 방법은 코드가 더 길어지니까 좋은 방법은 아니긴 한데…

1. 라면사는 순서를 바꿔도 결과는 똑같다. 그러니까 맨 앞부분부터 사도 괜찮다.
2. b <= c 의 경우 낱개로 사면 되는데 이 경우 Trivial 하다.
3. i-1 번째 라면가게까지 최적으로 라면을 모두 샀다고 하자. i번째부터 세가게가 x1, x2, x3 만큼 라면을 팔 때
   • x2 < x1 이면 x1 은 x1-x2 만큼은 혼자서 처리해야한다. 먼저 처리해놓으면 x1 <= x2 를 만족하고 아래 조건 중 하나에 들어간다. 만약 이 과정에서 x1==0 이 된다면 i 번째 라면도 최적으로 샀으므로 증명완료이다. 아래에서도 이와 비슷한 전략을 사용한다.
   • x3 <= x1 <= x2 식이라면 x1 은 x1-x3 만큼 x3 과 관계없이 처리해야한다. 이때 x2 도 같이 구매하는게 이득이다. 이 과정에서 x1 을 모두 구매하거나 아래 조건들 중에 들어간다.
   • x1 <= x3 <= x2 식이라면 x2 은 x2-x3 만큼 x3 과 관계없이 처리해야한다. 이때 x1 와 같이 구매하는게 이득이다. 이 과정에서 x1 을 모두 구매하거나 아래 조건에 들어간다.
   • x1 <= x2 <= x3 에서는 Greedy 전략이 통한다. x1 만큼 b+c+c 를 지불하면 최적으로 구매하게 된다.

시간 복잡도

O(\(\mathrm{N}\))

코드

using ll = long long;
int arr[1000003];

int main()
{
	int n; cin >> n; 
	ll b, c; cin >> b >> c;
	ll ans = 0;
	for (int i = 0; i < n; i++) cin >> arr[i];

	if (b <= c) {
		for (int i = 0; i < n; i++) ans += arr[i];
		ans *= b;
	}
	else {
		ll bc = b + c, bcc = bc + c;
		for (int i = 0; i < n; i++)
		{
			if (arr[i] == 0) continue;
			if (arr[i] > arr[i + 1])
			{
				int d = arr[i] - arr[i + 1];
				arr[i] -= d;
				ans += d * b;
			}
			if (arr[i] > arr[i + 2])
			{
				int d = arr[i] - arr[i + 2];
				arr[i] -= d; arr[i + 1] -= d;
				ans += d * bc;
			}
			if (arr[i + 1] > arr[i + 2])
			{
				int d = min(arr[i + 1] - arr[i + 2], arr[i]);
				arr[i] -= d; arr[i + 1] -= d;
				ans += d * bc;
			}
			if (arr[i + 1] <= arr[i + 2])
			{
				int d = arr[i];
				arr[i] -= d; arr[i + 1] -= d; arr[i + 2] -= d;
				ans += d * bcc;
			}
		}
	}
	cout << ans;
}