백준 1082번 방 번호 C++

문제

각 방에 0부터 N까지 숫자와 방의 가격 P가 부여된다. 방은 중복해서 구매할 수 있으며, 구매한 방 번호를 조합하여 가장 큰 숫자를 만드는 문제이다.

해설

문제에서 0은 가장 앞에 오면 안된다. 그렇다면, 하나만 고려해주면된다.  0번 방의 가격이 가장 작을 때와 그렇지 않을 때. 

즉 0~N 번 방에서의 최소 가격과 1~N 번 방의 최소 가격을 따로 구해준다.

1~N번 방에서 현재 자금으로 구매가 안되면, 답은 0이다. (0은 맨 앞에 올 수 없기 때문에)

 

들어가기에 앞서서 원래의 값을 저장해둘 배열과 방의 가격이 낮은 순서대로 배치될 수 있는 우선순위큐(pair<int, int>)를 준비한다.

문제 푸는 방법을 순서대로 나열한다면, 

1.  문제의 입력값을 받는다. 우선순위큐와 배열에 각각 받은 값을 넣어준다.
2. 우선순위큐의 top()을 저장하고 방 번호를 확인
   1. 방 번호가 0일 경우에, 우선순위 큐를 pop()하고, 다음 순위의 정보를 받아서 이를 정답 배열에 저장한다. 그리고 0번 방을 구매할 수 있는 만큼 구매한다.
   2. 그렇지 않은 경우, 구매할 수 있는 만큼 모두 구매한다.
3. 이제 맨 앞부터 차례대로 기존 값을 저장해둔 배열에서 방번호가 큰 순으로 구매 가능여부 확인 후, 방번호를 더 크게 만들 수 있도록 확인하면서 돈을 다 사용하거나, 인덱스를 넘어갈 때까지 확인해준다.
   1. 기존에 저장해둔 배열의 N번 째부터 내려오면서 확인
   2. 지금의 숫자가 확인한 방번호 보다 크거나 같으면 다음 순서로 넘어간다.

코드

#include <iostream>
#include <queue>
#include <string>

#define kit ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;
typedef pair<int,int> pii;

priority_queue<pii, vector<pii>, greater<pii>> mi;
int n, m, p[50], c[50], cnt=0;
string ans = "";

int main() {
    kit cin >> n;
    for (int i=0; i<n; i++) {
        cin >> p[i];
        mi.push({p[i], i});
    }
    cin >> m;
    
    pii cur = mi.top(); // 가장 싼방번호 저장
    if (cur.second == 0) {
        mi.pop();
        if (mi.top().first > m) { //구매할 수 없을 때 0
            cout << 0;
            return 0;
        }
    }
    
    m -= mi.top().first; c[cnt] = mi.top().first;
    ans += to_string(mi.top().second);
    cnt++;
    
    while (m >= cur.first) { // 제일 싼 거로 남은 부분 모두 채워줌
        m -= cur.first;
        ans += to_string(cur.second);
        c[cnt] = cur.first; cnt++;
    }

    int j=0;
    // 앞에서부터 큰 수로 바꿀 수 있는지 확인해줌
    // 더이상 구매할 수 없을 때, 범위를 나갔을 때,
    while(j < ans.length())
    {
        for (int i=n-1; i>0; i--)
        {
            // 구매할 필요가 없는 경우
            if ((int)ans[j] - '0' >= i) break;
            if (m + c[j] >= p[i]) { // 갱신할 돈을 구매할 수 있으면 구매함
                ans[j] = (char)(i + 48);
                m = m - (p[i] - c[j]);
                c[j] = p[i];
                break;
            }
        }
        j++;
    }
    
    for (char a : ans) cout << a;
}

 

구매 여부 확인에 대해 일단 1~N 까지의 방에서 가장 싼 값의 방과, 0~N까지에서의 가장 값싼 방을 구하는, 두 가지의 경우를 나눠서 생각하지 못해서 처음에 시간이 오래 걸렸다. 해당 아이디어를 얻고 그리디로 문제를 풀면 깔끔하게 해결할 수 있다.