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

코딩테스트/그리디|힙

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

유(YOO) 2023. 9. 28. 14:51

https://www.acmicpc.net/problem/18185

18185번: 라면 사기 (Small)

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i

www.acmicpc.net

v[i+1] > v[i+2]이면 v[i+1]을 5원으로 먼저 사기(나중에 3원, 3원 사는 것보다 적은 금액으로 살 수 있다)

#include <iostream>
#include <vector>

using namespace std;

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

    int n;
    cin >> n;

    vector<int> v(n+2, 0);
    for(int i=0; i<n; i++) cin >> v[i];

    int answer = 0;
    int cnt = 0;
    for(int i=0; i<n; i++) {
        if (v[i+1] > v[i+2]) { // v[i+2]를 먼저 구매하면 다음 연속 끊김
            cnt = min(v[i], v[i+1] - v[i+2]); // v[i+2]는 다음에 구매 가능
            answer += cnt * 5;
            v[i] -= cnt;
            v[i+1] -= cnt;

            cnt = min(v[i], min(v[i+1], v[i+2]));
            answer += cnt * 7;
            v[i] -= cnt;
            v[i+1] -= cnt;
            v[i+2] -= cnt;

        }
        else {
            cnt = min(v[i], min(v[i+1], v[i+2]));
            answer += cnt * 7;
            v[i] -= cnt;
            v[i+1] -= cnt;
            v[i+2] -= cnt;

            cnt = min(v[i], v[i+1]);
            answer += cnt * 5;
            v[i] -= cnt;
            v[i+1] -= cnt;
        }

        answer += v[i] * 3;
    }

    cout << answer;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

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

    long long n, b, c;
    cin >> n >> b >> c;

    vector<int> v(n+2, 0);
    for(int i=0; i<n; i++) cin >> v[i];

    long long answer = 0;
    long long cnt = 0;

    if (b < c) { // 종료
        for(int i=0; i<n; i++) answer += v[i];
        cout << answer * b;
        return 0;
    }

    for(int i=0; i<n; i++) {
        if (v[i+1] > v[i+2]) { // v[i+2]를 먼저 구매하면 다음 연속 끊김
            cnt = min(v[i], v[i+1] - v[i+2]); // v[i+2]는 다음에 구매 가능
            answer += cnt * (b + c);
            v[i] -= cnt;
            v[i+1] -= cnt;

            cnt = min(v[i], min(v[i+1], v[i+2]));
            answer += cnt * (b + 2 * c);
            v[i] -= cnt;
            v[i+1] -= cnt;
            v[i+2] -= cnt;

        }
        else {
            cnt = min(v[i], min(v[i+1], v[i+2]));
            answer += cnt * (b + 2 * c);
            v[i] -= cnt;
            v[i+1] -= cnt;
            v[i+2] -= cnt;

            cnt = min(v[i], v[i+1]);
            answer += cnt * (b + c);
            v[i] -= cnt;
            v[i+1] -= cnt;
        }

        answer += v[i] * b;
    }

    cout << answer;

    return 0;
}