https://www.acmicpc.net/problem/18185
다이아 문제중에 해볼만한 문제로 가져와봤습니다.
1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i + 1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N - 1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i + 1)번 공장, (i + 2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N - 2). 이 경우 비용은 7원이 든다.
우선 라면을 구매할 수 있는 방법은 이렇게 3가지입니다.
i번째 공장에서는 남아있는 모든 라면을 구매하는게 맞겠고,
i + 1, i + 2번째 공장의 라면을 가능하면 추가로 구매하는게 더 좋습니다.
제가 구현한 방식은 i번째 라면은 개당 3원씩 모두 구매하고, i + 1, i + 2번째 라면을 구매할때마다 2원을 추가하는 방식으로 구현했습니다.
하지만 i ~ i + 2 범위 내에 가능한 모든 라면을 구매한다면 반례가 존재합니다.
4
1 2 1 1여기서 가능한대로 모든 라면을 구매한다고 했을 때 1 ~ 3번째 공장에서 라면을 구매했을 것입니다. (소모한 금액: 7)
0 1 0 1그러면 남은 라면은 이렇게 될 것이고, 남은 공장에서 하나씩 구매한다면 7 + 3 + 3 = 13의 금액이 필요합니다.
하지만 처음에 3번 공장에서 구매하지 않는다면
0 1 1 11, 2번째 공장에서만 라면을 구입하고, (소모한 금액: 5)
나머지 2 ~ 4번째 공장에서 라면을 구입한다면 5 + 7 = 12의 금액이 필요하여 이게 최소가 됩니다.
따라서 하나더 고려해야할 부분은 최초 필요한 갯수가 list[i + 1] > list[i + 2] 이라면
"i + 1번째 공장에서 남긴 수만큼 i + 2번째 공장에서도 남겨야 한다"가 됩니다.
물론 i + 1번째 공장에서는 가능한 라면을 모두 구매하는 것이 맞습니다.
이 부분만 고려를 해준다면 문제없이 이 문제를 해결할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <iostream>
#include <algorithm>
#define MAX 10010
using namespace std;
int list[MAX];
int N;
void func() {
int ret = 0;
for (int i = 0; i < N; i++) {
if (!list[i]) continue;
int cnt = list[i];
list[i] = 0;
ret += (3 * cnt);
if (i + 1 >= N) continue;
cnt = min(cnt, list[i + 1]);
list[i + 1] -= cnt;
ret += (2 * cnt);
if (i + 2 >= N) continue;
if (cnt + list[i + 1] > list[i + 2]) {
cnt = min(cnt, max(0, list[i + 2] - list[i + 1]));
}
list[i + 2] -= cnt;
ret += (2 * cnt);
}
cout << ret << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 14464 소가 길을 건너간 이유 4 (0) | 2024.07.05 |
|---|---|
| boj 1263 시간 관리 (0) | 2024.07.03 |
| boj 16120 PPAP (0) | 2021.10.16 |
| boj 2262 토너먼트 만들기 (0) | 2021.10.16 |
| boj 13904 과제 (0) | 2021.09.30 |