[Algorithm] 백준 18185 라면 사기 (Small) - C++, 그리디

18185번: 라면 사기 (Small)

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

int factorys[10003];
int n;
int answer = 0;

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> factorys[i];

    // solve
    for(int i = 1; i <= n; i++){
        // 3개 불가능
        if(factorys[i+1] > factorys[i+2]){
            int count = min(factorys[i], factorys[i+1] - factorys[i+2]);
            answer += 5*count;

            factorys[i] -= count;
            factorys[i+1] -= count;

            int count2 = min(factorys[i], min(factorys[i+1], factorys[i+2]));
            answer += 7*count2;

            factorys[i] -= count2;
            factorys[i+1] -= count2;
            factorys[i+2] -= count2;
        } 
        else{ 
            // 3개 가능
            int count = min(factorys[i], min(factorys[i+1], factorys[i+2]));
            answer += 7*count;

            factorys[i] -= count;
            factorys[i+1] -= count;
            factorys[i+2] -= count;

            int count2 = min(factorys[i], factorys[i+1]);
            answer += 5*count2;

            factorys[i] -= count2;
            factorys[i+1] -= count2;
        }
        answer += 3*factorys[i];
        factorys[i] = 0;
    }

    cout << answer << '\n';
}

---

 평소 눈여겨 보던 다이아 문제였는데 풀 수 있어서 정말 기분이 좋았네요. 일단 문제에서 최대한 연속된 구매를 하는게 무조건 이득입니다. 개당 단가가 3개 7원이 제일 싸기 때문에 최대한 싸게 구매할 수 있게 해야 합니다. 

 그리고 연속된 구매를 하는 것이기 때문에 i = 1에서 시작해 순차적으로 그리디하게 보면 됩니다. 그리디의 과정은 아래 순서를 가게 됩니다.

 

- 3개 연속으로 살 수 있는가?

   - 살 수 있다면 i+1 < i+2 인가?

      - i+2 가 더 크다면 일단 i, i+1, i+2 에서 가장 작은 값대로 구매를 해줍니다.

         - 이후 5개 구매를 할 수 있는 만큼 i, i+1 에서 구매를 해줍니다.

      - i+1이 더 크다면 일단 [i+1]-[i+2] 계산을 해서 7개를 구매할 여지를 남겨둔 채 5개 구매를 합니다.

         - 그 후 7개를 구매할 수 있다면 구매를 해 줍니다.

- 이후 남은 갯수를 1개 구매로 처리해 줍니다. 연속되는 공장이 없으면 어차피 3원에 사야하니깐요.

 

 일단 최대한 7개를 위주로 사고 그게 안되면 5개를 최소한 구매 후 7개 구매, 그래도 안된다면 1개를 구매하는 방식으로 하면 됩니다.