문제
https://www.acmicpc.net/problem/18185
문제이해
- 라면 공장의 수인 N을 입력받고 i번 공장에서 구매할 라면의 수를 공백을 두고 입력한다(1 ≤ i ≤ N).
- 출력으로 교준이가 필요한 최소 금액을 출력한다.
교준이가 라면을 구매하는 규칙을 보자면,
- i번째 공장에서 라면 한 개를 구매하는 가격은 3원
- i번째 공장과 i+1번째 공장에서 라면을 한개씩 구매할 때 총가격은 5원
- 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개씩 묶는게 더 이득일 때도 있지 않을까? 라는 생각을 다행히 할 수 있었고 조건을 찾아 문제 해결을 성공하였다.
'Coding' 카테고리의 다른 글
[C++]백준 5430번: AC (0) | 2023.07.11 |
---|---|
[C++]백준 2258번: 정육점 (0) | 2023.07.11 |
[C++]백준 1182번: 부분수열의 합 (0) | 2023.07.09 |
[C++]백준 2644번: 촌수계산 (0) | 2023.07.08 |
[C++]백준 10816번: 숫자 카드 2 (0) | 2023.07.07 |