문제 간략 설명

N개의 라면 공장이 있고, 각 공장에서 정확하게 정해진 개수의 라면을 구매해야 한다. 라면 1개를 사면 B원, i번과 (i+1)번 공장에서 각각 1개씩 사면 (B+C)원, i번과 (i+1)번, (i+2)번 공장에서 각각 1개씩 사면 (B+2C)원이 든다. 최소 비용으로 라면을 구매하는 프로그램을 작성하시오.

풀이 방법

  1. C >= B인 경우 묶어서 샀을 때의 이득이 전혀 없다. 입력 * B 의 합을 출력한다.
  2. C < B인 경우는 3개 > 2개 > 1개 묶음 순으로 이득이다. 2개 + 2개 살 때와 3개 + 1개 살 때 비용이 2B + 2C로 동일하나 2개로 묶는게 이후 묶음의 가능성을 남겨놓을 수 있다. 18185와 로직이 동일하다.

코드

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ll;

int N;
ll B, C;
int arr[3];
ll sum = 0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> B >> C;

	if (C >= B) {
		for (int i = 0; i < N; i++) {
			cin >> arr[0];
			sum += arr[0] * B;
		}
		cout << sum << endl;
		return 0;
	}

	for (int i = 0; i < N; i++) {
		cin >> arr[i % 3];

		if (i < 2) continue;
		
		int n1 = arr[(i - 2) % 3];
		int n2 = arr[(i - 1) % 3];
		int n3 = arr[i % 3];

		int m;

		if (n2 > n3) {
			m = n2 - n3;
			m = min(m, n1);

			n1 -= m; n2 -= m; sum += m * (B + C);
		}

		m = min(n1, n2);
		m = min(m, n3);

		n1 -= m, n2 -= m, n3 -= m, sum += m * (B + 2 * C);

		m = min(n1, n2);

		n1 -= m; n2 -= m, sum += m * (B + C);

		sum += n1 * B, n1 = 0;

		arr[(i - 1) % 3] = n2;
		arr[i % 3] = n3;
	}

	int n1 = arr[(N - 2) % 3], n2 = arr[(N - 1) % 3];

	int m = min(n1, n2);

	n1 -= m; n2 -= m, sum += m * (B + C);

	sum += (n1 + n2) * B;

	cout << sum << endl;

	return 0;
}

Key Points