라면 사기

백준 18185번: 라면 사기 (Small)
백준 18186번: 라면 사기 (Large)

아이디어

1개를 사면 3원, 2개를 사면 5원, 3개를 사면 7원이다.
라면 1개를 사는 대신 2개를 사는 경우, 개당 가격이 3원에서 2.5원으로 0.5원 줄어든다. 라면 2개를 사는 대신 3개를 사는 경우, 개당 가격이 2.5원에서 2.333..원으로 0.166..원 줄어든다.
따라서 i번째 라면을 어떤 가격에 구매할 지 결정할 때, i-1번째 라면을 개당 3원에 산 경우를 최대한 줄여서 둘 다 2.5원에 산걸로 만들고, 이후 남은 i번째 라면으로 i-1, i-2번째 라면을 개당 2.5원에 산 경우를 최대한 줄여서 셋 다 2.333..원에 산걸로 만든다. 그러고도 i번째 라면이 남으면 그건 개당 3원에 산다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, B = 3, C = 2, ANS = 0;
vector<int> v, cnt; // cnt: B+C

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

    cin >> N;
    v = vector<int>(N);
    cnt = vector<int>(N);
    for(int i = 0; i < N; i++) {
        cin >> v[i];
    }

    ANS += B*v[0];

    for (int i = 1; i < N; i++) {
        int m = min(v[i], v[i-1]); // B -> B+C
        v[i] -= m;
        cnt[i] += m;
        ANS += C*m;

        m = min(v[i], cnt[i-1]); // B+C -> B+2C
        v[i] -= m;
        ANS += C*m;

        ANS += B*v[i]; // B
    }

    cout << ANS;

    return 0;
}

3원 5원 7원을 B원, B+C원, B+2C원으로 일반화한 문제가 18186번 문제다.
B < C인 경우는 죄다 1개씩 사면 되고, 그 외에는 18185번 문제처럼 처리해주면 된다

#include <bits/stdc++.h>

using namespace std;

int N, B, C;
long long ANS = 0;
vector<long long> v, cnt; // cnt: B+C

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

    cin >> N >> B >> C;
    v = vector<long long>(N);
    cnt = vector<long long>(N);
    for(int i = 0; i < N; i++) {
        cin >> v[i];
    }

    if (B <= C) {
        for (int i = 0; i < N; i++) {
            ANS += B*v[i];
        }
    }

    else {
        ANS += B*v[0];
        for (int i = 1; i < N; i++) {
            long long m = min(v[i], v[i-1]); // B -> B+C
            v[i] -= m;
            cnt[i] += m;
            ANS += C*m;

            m = min(v[i], cnt[i-1]); // B+C -> B+2C
            v[i] -= m;
            ANS += C*m;

            ANS += B*v[i]; // B
        }
    }

    cout << ANS;

    return 0;
}

여담

그리디 넘 어렵다. 종만북에 내가 짠 그리디 알고리즘이 정당한지 간단하게 증명하는 방법이 적혀있었는데 쉬운 문제라도 증명하면서 푸는 연습을 하면 좋을 것 같다.
문제 딱 봤을때 바로 DP인지 그리디인지 알 수 있도록 공부해야할듯.