2022. 10. 4. 13:42ㆍC++/알고리즘
그리디 알고리즘(탐욕 알고리즘)은 알고리즘을 풀어나갈때 각 순간마다 최적인 답을 선택하여서 최적해의 근사값을 구하는 알고리즘이다.
그리디 알고리즘으로 추론된 답이 최적해임을 보장하기 위해선 문제가 두 가지 조건을 만족하여야 한다.
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 |