문제 간략 설명

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

풀이 방법

  1. 입력이 10^4까지 들어오니까 입력을 받으면서 계산.
  2. arr[3] 안에서 %를 이용해 greedy로 처리.
  3. 각 i에 대해서 i, i+1, i+2를 n1, n2, n3로 계산한다. n2 > n3일 경우 그 차이만큼 2개 구매한다 (5 + 5, 7 + 3 동일하지만 이후 묶어서 살 가능성 존재). 이후 가능한만큼 3개 구매, 2개 구매, 1개 구매 순으로 계산한다. 마지막 2개 남았을 때 따로 계산한다.

코드

#include <iostream>
#include <cmath>

using namespace std;

int N;
int arr[3];
unsigned long long sum = 0;

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

	cin >> N;

	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 * 5;
		}

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

		n1 -= m, n2 -= m, n3 -= m, sum += m * 7;

		m = min(n1, n2);

		n1 -= m; n2 -= m, sum += m * 5;

		sum += n1 * 3, 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 * 5;

	sum += n1 * 3 + n2 * 3;

	cout << sum << endl;

	return 0;
}

Key Points