[BOJ] 1082 - 방 번호

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

BOJ - 방 번호

문제 유형: 다이나믹 프로그래밍, 그리디

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 128MB

 

문제

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

 

입력

첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다.

 

출력

첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

 

풀이

dp[i] = i원이 남았을 때의 최선의 suffix로 한다.

처음에는 0이 오면 안되기에, 9~1을 붙여서 dfs를 시도한다.

현재 남은 예산으로 아무것도 살 수 없다면, ""를 리턴하여 종료시키고, 아니라면, 그리디하게 9~1순서로 재귀 호출시켜서 가장 큰 suffix를 만들어낸다.

dp테이블에 저장시키며 리턴한다.

 

숫자는 long long형으로도 못 담는다. 즉, 문자열 숫자로 구성하고 대소비교를 해줘야 한다.

a가 b보다 크거나 같은지 확인하는 ge함수를 참조하자. 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, minimum;
vector<string> numtostr = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};

bool ge(const string& a, const string& b) {
    if (a.size() < b.size()) return false;
    if (a.size() > b.size()) return true;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] < b[i]) return false;
        if (a[i] > b[i]) return true;
    }

    return true;
}

string solve(int remain, vector<int>& p, vector<string>& dp) {
    if (remain < minimum) {
        return "";
    }

    if (dp[remain] != ".") {
        return dp[remain];
    }

    string res = "";
    for (int i = n - 1; i >= 0; i--) {
        if (remain >= p[i]) {
            string temp = numtostr[i] + solve(remain - p[i], p, dp);
            if (ge(temp, res)) {
                res = temp;
            }
        }
    }
    return dp[remain] = res;
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin >> n;
    vector<int> p(n);
    for (auto& i : p) cin >> i;
    cin >> m;
    minimum = *min_element(p.begin(), p.end());

    vector<string> dp(m + 1, ".");

    string res = "";
    for (int i = n - 1; i > 0; i--) {
        if (m >= p[i]) {
            string temp = numtostr[i] + solve(m - p[i], p, dp);
            if (ge(temp, res)) {
                res = temp;
            }
        }
    }
    if (res == "") {
        cout << "0\n";
    } else {
        cout << res << "\n";
    }

    return 0;
}