[Algorithm] 백준 18186 라면 사기 (Large)

18186번: 라면 사기 (Large)

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

long long factorys[1000003];
long long n, b, c;
long long answer = 0;

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

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

    // solve
    // select b is better choice
    if(b < c){
        for(int i = 1; i <= n; i++)
            answer+= factorys[i];
        cout << answer*b << '\n';
        return 0;
    }

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

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

            long long count2 = min(factorys[i], min(factorys[i+1], factorys[i+2]));
            answer += (b+2*c)*count2;

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

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

            long long count2 = min(factorys[i], factorys[i+1]);
            answer += (b+c)*count2;

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

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

---

 

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

 위 문제의 다음으로 아래 3가지만 해주면 됩니다.

 

- 배열의 크기를 늘려준다

- 데이터 타입을 long long으로 늘려준다

- b < c 인 경우가 있어 만일 c 가 더 비쌀 경우 모두 b 로 구매하도록 처리한다

 

위 18185 풀이를 보고 오신 분들이나 푸신 분들은 위 3개만 적용하면 금방 풀이하실 수 있습니다!