Greedy

백준 18186번 라면사기(large) 문제풀이

[18186 라면사기(large)] https://www.acmicpc.net/problem/18186 .
그리디하게 문제를 해결해보자!

사람들이 많이 푼 다이아 문제 중 하나라서 언젠가 꼭 풀어봐야지 했던 문제다.
좀 보면 그리디라는 건 쉽게 알아차릴 수 있다.
근데 다른사람들도 많이 그랬던데 단순히 3개를 사는 걸 먼저하면 틀린다.
그리디를 어떻게 해야할지가 꽤 까다로운 문제였다.

문제상황 파악하기.

위에서 얘기 했던대로 라면 사는 걸 7원으로 사는게 가장 이득이니까 단순히 그것부터 하면 틀린다.
대표적인 반례는 B = 3, C = 2일 때 1 2 1 1이 있고 이는 0 1 1 1 로 바꾸고 0 0 0 0으로 바꾸는게 이득이다.
단순히 0 1 0 1로 바꾸면 곤란해진다.
이렇게 되는 이유는 1 2 1 에서 2가 마지막 1보다 크기 때문이다.
이를 어떻게 해결해야 할까?

아이디어 얻기.

i+1번째 라면 공장에서 라면을 살때 i-1, i, i+1 중에서 i가 i+1보다 크면, i를 먼저 처리하는 게 중요하다.
근데 사실 i+1번째 공장에서 사야할 라면이 더 많아도 i를 먼저 처리해주면 된다.
그러니 B로 산 행위를 B+C로 바꾸는 걸 먼저해줘도 된다는 뜻이다.
등차수열이니 이렇게 된다.
이게 더 이득인 이유를 대충 말해보면 그 다음 i+2로 가면 B로 따로 사는 것보다 B+C를 B+2C로 바꾸는게 이득이니까 그 가능성을 더 늘리는 것이다.
따라서 아래와 같이 내 구입목록 클래스를 만들었다.

class purchase{
public:
    //first = B로 산거 다음에 B+C로 업글
    //second = B+C로 산거 다음에 B+2C로 업글
    // third = B+2C로 산거.
    int first= 0, second= 0, third=0;
    ll res = 0;
};

이전에 first 행동을 second행동으로 바꾸는 걸 제일 먼저,
그 다음에 second 행동을 third 행동으로 바꾸는게 두번째, 마지막은 그냥 낱개로 사는 first행동을 하는게 세번째 순으로 i+1번째의 최소 비용을 계산하면 된다.

주의할 점

당연히 메모리와 시간을 주의해야한다.
이전에 샀던 현황으로 이번에 살꺼를 정하는 과정에서 while문을 사용하여 하나씩 처리하면 시간초과고 한번에 계산하면 된다. O(N^2) -> O(N)
small에서는 while문으로 해도 통과했는데 large는 n의 제한이 커지니 당연히 통과하지 않았따.
난 C가 B보다 클때를 고려하지 않아서 한번 틀렸다.
그냥 C가 B보다 크면 C를 B로 바꾸는 문장 하나 넣으니까 맞았다.

실제 코드

나머지 주의 할 점은 코드에 주석으로 처리했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

class purchase{
public:
    //first = B로 산거 다음에 B+C로 업글
    //second = B+C로 산거 다음에 B+2C로 업글
    // third = B+2C로 산거.
    int first= 0, second= 0, third=0;
    ll res = 0;
};
int n;
ll B, C;
vector<int> a;

int main(){
    fast_io
    cin >> n >> B >> C;
    C = min(C, B);  //C가 B보다 크면 다 B롤 사는게 이득이잖아 ㅋㅋ
    a = vector<int> (n+1);
    for(int i=1;i<=n;i++) cin >> a[i];
    purchase myP[2];
    for(int i=1;i<=n;i++){
        if (myP[0].first&&a[i]) {
            int diff = min(myP[0].first, a[i]);
            myP[1].second += diff;
            myP[0].res -= 1LL*B*diff;
            myP[1].res += (B+C)*diff;
            a[i] -= diff;
        }
        if(myP[0].second&&a[i]) {
            int diff = min(myP[0].second, a[i]);
            myP[1].third += diff;
            myP[0].res -= 1LL*(B+C)*diff;
            myP[1].res += 1LL*(B+2*C)*diff;
            a[i] -= diff;
        }
        if (a[i]) {
            myP[1].first += a[i];
            myP[1].res += 1LL*B*a[i];
            a[i] = 0;
        }
        myP[1].res += myP[0].res;
        myP[0] = {0, 0, 0, 0};
        swap(myP[0],myP[1]);
    }
    cout << myP[0].res;
}

Greedy

백준 18186번 라면사기(large) 문제풀이

문제상황 파악하기.

아이디어 얻기.

주의할 점

실제 코드

Leave a comment

2024

2023

2022