라면 사기(그리디 알고리즘)

2022. 10. 4. 13:42C++/알고리즘

 그리디 알고리즘(탐욕 알고리즘)은 알고리즘을 풀어나갈때 각 순간마다 최적인 답을 선택하여서 최적해의 근사값을 구하는 알고리즘이다.

 

 그리디 알고리즘으로 추론된 답이 최적해임을 보장하기 위해선 문제가 두 가지 조건을 만족하여야 한다.

 

1. 탐욕적 선택 속성: 탐욕적인 선택이 언제나 최적해를 보장해야 함(특정 선택이 이후의 선택에 영향을 주지 않음).

2. 최적 부분 구조: 문제의 최적해는 부분 문제들의 최적해의 집합과 동일하여햐 함.

 

https://www.acmicpc.net/problem/18185

 

18185번: 라면 사기 (Small)

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i

www.acmicpc.net

 백준 18185번 라면사기 문제가 그리디 알고리즘으로 최적해를 구할 수 있다.

 i, i+1, i+2번째 공장에서 라면을 구매할때는 i -> i+1 -> i+2 순서로 라면의 유무를 파악하므로 추후 i+1이 기준이 되는 탐욕적인 방법에서의 선택에 영향을 끼치지 않을 것이다.

 라면을 더 많이 살 수록 금액이 적어지므로 각 부분들의 최적해의 합이 전체 문제의 최적해로 도출될 수 있다.

 

다만 딱 한 가지 반례가 있기 때문에 유의하여야 한다.

 

i i+1 i+2 i+3 합계
1 2 1 1 0
0 1 0 1 7
0 0 0 1 10
0 0 0 0 13

 

i i+1 i+2 i+3 합계
1 2 1 1 0
0 1 1 1 5
0 0 0 0 12

 

i+1번째 공장에서 구매할 라면 갯수보다 i+2번째 공장에서 구매할 라면 갯수가 더 적을때(i+1 > i+2)

i, i+1, i+2 공장에서 라면을 전부 사게되면 i+1과 i+3의 연결이 끊어지기 때문에 오히려 더 많은 돈을 지불하여야 한다.

 

탐욕적인 방법을 선택할때 i+1과 i+2의 연결이 최대한 유지되어야 함에 주의하여야 한다.

 

#include<iostream>
using namespace std;

int Ramen[10001] = { 0, };

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

	int n;
	cin >> n;

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

	int ret = 0;

	for (int i = 0; i < n; i++)
	{
		while (Ramen[i])
		{
			if (i + 1 < n &&
				Ramen[i + 1] > 0)
			{
				if (i + 2 < n &&
					Ramen[i + 2] > 0 &&
					Ramen[i + 1] <= Ramen[i + 2])
				{
					Ramen[i]--;
					Ramen[i + 1]--;
					Ramen[i + 2]--;
					ret += 7;
				}
				else
				{
					Ramen[i]--;
					Ramen[i + 1]--;
					ret += 5;
				}
			}
			else
			{
				Ramen[i]--;
				ret += 3;
			}
		}
	}

	cout << ret << '\n';
}

'C++ > 알고리즘' 카테고리의 다른 글

계단 오르기(다이나믹 프로그래밍)  (0) 2022.10.04
컵라면(그리디 알고리즘)  (1) 2022.10.04
백조의 호수(BFS 최적화)  (0) 2022.08.31
우선순위 큐(Priority Queue)  (0) 2022.08.30
다이나믹 프로그래밍  (0) 2022.08.29