boj 18185 라면 사기 (Small)

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 1

1, 2번째 공장에서만 라면을 구입하고, (소모한 금액: 5)

나머지 2 ~ 4번째 공장에서 라면을 구입한다면 5 + 7 = 12의 금액이 필요하여 이게 최소가 됩니다.

 

따라서 하나더 고려해야할 부분은 최초 필요한 갯수가 list[i + 1] > list[i + 2] 이라면

"i + 1번째 공장에서 남긴 수만큼 i + 2번째 공장에서도 남겨야 한다"가 됩니다.

물론 i + 1번째 공장에서는 가능한 라면을 모두 구매하는 것이 맞습니다.

이 부분만 고려를 해준다면 문제없이 이 문제를 해결할 수 있습니다.

 

 

#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;
}