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

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

 

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

 

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

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

 

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

18185번: 라면 사기 (Small)

 백준 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';
}