BOJ 18185 라면 사기 (Small)

(1) 문제 설명

분류 : greedy

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

(1000 이하) N개의 공장에서 구매해야하는 라면의 갯수가 각각 들어옵니다.
i 번 공장에서 라면을 1개 구매할 때는 3의 비용이,
i 와 i+1 번 공장에서 라면을 1개 구매할 때는 5의 비용이,
i, i+1, i+2 번 공장에서 라면을 1개 구매할 때는 7의 비용이듭니다.

각 공장에서, 정확히 정해진 양만큼 구매를 진행한다고 했을 때,
비용의 최솟값을 구하시오.

(2) Wrong Answer 코드

인접한 2개의 공장에서의 라면 1개를 구매하는 것은 한번에 구매하는게 이득이며,
가능하다면 3개의 공장에서 같이 구매하는 게 더 이득입니다.

인접한 3개의 공장의 남은 라면의 min 값으로 구매를 하고,
인접한 2개의 공장의 라면의 min 값으로 구매를 하고,
남은 것 만큼의 라면을 구매하면 적당히 좋은 값이 나올 것 같습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int r[10000];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d", &r[i]);
	long long ans = 0, t;
	for (int i = 0; i < n; i++) {
		if (i + 2 < n) {
			t = min({ r[i], r[i + 1], r[i + 2] });
			r[i + 2] -= t;
			r[i + 1] -= t;
			r[i] -= t;
			ans += t * 7;
		}
		if (i + 1 < n) {
			t = min(r[i], r[i + 1]);
			r[i + 1] -= t;
			r[i] -= t;
			ans += t * 5;
		}
		if (r[i]) ans += 3 * r[i];
	}
	printf("%lld\n", ans);
}

(3) 풀이 도출

위의 제안한 방법에 해당되지 않는 예외 케이스가 존재하는데요.
바로 아래의 케이스입니다.

문제의 솔루션을 제안하는 것 만큼 중요한 것은,
커버하지 못하는 경우가 있는지 확실히 알아야하는데요.
때론 손으로 직접 작성해보는 게 가장 효과적일 수 있습니다.

5
1 4 2 3 1

이 케이스를 커버하지 못하는 이유는,
근본적으로 솔루션의 오류가 있어서 인데요.

위 케이스의 최적은 다음과 같습니다.

1 1              (5)
  2 2 2          (7x2)
  1              (3)
      1 1        (5)
= 27

핵심은,
인접한 3개에서 때에 따라서는 2개짜리를 먼저 해야 하는 때가 있다는 건데요!
바로 i+1 과 i+2 의 관계를 조금 더 정리해보면 이 문제를 해결 할 수 있습니다.

(4) 정답 코드

BOJ 18185 라면 사기

쉽게 쓰는 : Easy To Use

BOJ 18185 라면 사기