[백준 C++] 18185 라면 사기 (Small) - 그리디

18185번: 라면 사기 (Small)

#include <iostream>
using namespace std;

int Factory[10002];

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

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> Factory[i];
	}

	int Price = 0;
	for (int i = 0; i < N; ++i)
	{
		int Num;
		if (Factory[i + 1] > Factory[i + 2])
		{
			Num = min(Factory[i], Factory[i + 1] - Factory[i + 2]);
			Price += Num * 5;
			Factory[i] -= Num;
			Factory[i + 1] -= Num;
		}

		Num = min(Factory[i], min(Factory[i + 1], Factory[i + 2]));
		Price += Num * 7;
		Factory[i] -= Num;
		Factory[i + 1] -= Num;
		Factory[i + 2] -= Num;

		Price += Factory[i] * 3;
	}

	cout << Price;
}

---

 

그리디 알고리즘 유형의 문제입니다.

모든 공장을 한번씩 순차 탐색해서 각 공장의 남은 라면 개수를 0으로 만들어주면 됩니다.

 

현재 i번 공장일 때,

i + 1번 공장이 i + 2번 공장보다 라면 개수가 많다면

5원어치(i, i + 1) 라면을 구매할 수 있는 만큼 구매해 i + 1번 공장의 개수를 i + 2번 공장의 개수와 맞추어줍니다.

그리고 7원어치(i, i + 1, i + 2) 라면을 구매할 수 있는 만큼 구매하고

마지막으로 3원어치(i) 라면을 구매할 수 있는 만큼 구매하면 됩니다.

 

그리고 주의할 점은 min연산을 이용해서 매번 구매할 수 있는 양의 라면만 구매하도록 하는 것입니다.