[C++]백준 18185번: 라면 사기 (Small)

문제

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

18185번: 라면 사기 (Small)

문제이해

• 라면 공장의 수인 N을 입력받고 i번 공장에서 구매할 라면의 수를 공백을 두고 입력한다(1 ≤ i ≤ N).
• 출력으로 교준이가 필요한 최소 금액을 출력한다.

교준이가 라면을 구매하는 규칙을 보자면,

1. i번째 공장에서 라면 한 개를 구매하는 가격은 3원
2. i번째 공장과 i+1번째 공장에서 라면을 한개씩 구매할 때 총가격은 5원
3. i번째 공장과 i+1번째 공장과 i+2공장에서 라면을 한 개씩 구매할 때 총가격은 7원

이다.

 

이해하기 쉽게 1은 1번, 2는 2번, 3은 3번이라고 표현하겠다.

 

라면 1개당 가격은 1번의 경우이 3원, 2번은 5/2원, 3번은 7/3원이다.

연달아 있는 3개의 공장에서 라면을 구매해야 한다면 3번을 통해 7원을 주고 라면을 구매하는 게 무조건 이득인 것처럼 보이지만 아래의 반례는 7원을 주고 구입하는 것이 오히려 손해인 경우다.

4
3 5 2 0

연달아 있는 3개의 공장에서 라면을 1개 이상 구매해야 하기 때문에 3번을 채택할 경우

3 5 2 0

2 4 1 0

1 3 1 0

0 2 0 0

0 1 0 0

0 0 0 0

이다.

여기서 사용한 방법들을 나열하자면 3번 -> 3번 -> 3번 -> 1번 -> 1번 이다. 총가격은 7 +7 + 7 + 3 + 3 = 27원이다.

 

다음은 3번을 채택하지 않고 2번을 채택했을 경우이다.

3 5 2 0

2 4 2 0

1 3 2 0

0 2 2 0

0 1 1 0

0 0 0 0

이다.

여기서 사용한 방법들을 나열하자면 2번 -> 2번 -> 2번 -> 2번 -> 2번 이다. 총가격은 5 + 5 + 5 + 5 +5 = 25원이다.

 

이러는 이유를 설명해보려고 한다.

연달아 있는 3개의 공장 A B C에 대해서 구매해야 되는 라면의 양이 3 5 2 이다. B번 공장에서 구매해야 되는 라면의 양이 C번 공장에서 구매해야 되는 라면의 양보다 많다. 그런데 여기서 3번을 계속 사용할 경우 C번 공장에서 구매해야 될 라면은 전부 다 구매했지만 B번 공장에서는 구매해야 되는 라면이 아직 남아있게 된다. 남은 라면을 구매하기 위해 어쩔 수 없이 1번을 사용하게 될 것이고 오히려 라면을 한 개당 3원에 구입하며 비용을 더 늘리게 된다.

 

하지만 2번을 이용해 라면을 구매하면 C번 공장에서 구매해야할 라면을 모두 구매하기 전에 B번 공장의 라면을 A번 공장의 라면과 묶어 구매하며 비용을 줄일 수 있다.

 

따라서 연달아 라면을 구매해야 되는 공장이 3개가 존재할 때 2번째 공장의 라면의 양이 3번째 공장의 라면의 양보다 많을 경우 3번을 채택하는 것이 아닌 2번을 채택하여야 한다.

 

문제해결

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

vector<int> factory;

int cost{ 0 };

void buy(int idx, int size) {
	if (idx >= size) {
		return;
	}
	if (idx < size && factory[idx] != 0) {
		factory[idx]--;
		cost += 3;
		if (idx + 1 < size && factory[idx + 1] != 0) {
			int temp2 = factory[idx + 1];
			factory[idx + 1]--;
			cost += 2;
			if (idx + 2 < size && factory[idx + 2] != 0) {
				if (factory[idx + 2] >= temp2) {
					factory[idx + 2]--;
					cost += 2;
				}
			}
		}
		buy(idx, size);
	}
	else {
		buy(idx + 1, size);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, quan;
	cin >> N;
	for (int i{ 1 }; i <= N; i++) {
		cin >> quan;
		factory.push_back(quan);
	}
	buy(0, N);
	cout << cost;
}

문제후기

반례를 찾지못해 문제가 오답이 나와 매우 어려웠다. 3개씩 묶는 것보다 2개씩 묶는게 더 이득일 때도 있지 않을까? 라는 생각을 다행히 할 수 있었고 조건을 찾아 문제 해결을 성공하였다.