[DP] BOJ 1082_방번호

문제 링크 : www.acmicpc.net/problem/1082

1082번: 방 번호

 

DP의 대표적 유형인 거스름돈 문제와 유사한 문제이다.

 

숫자를 구매하여 높은 숫자를 만드는 방법은 두 가지가 있다.

 1. 자릿수가 높은 숫자를 만든다. (ex. 11111 > 9999)

 2. 자릿수가 같다면, 값이 높은 숫자를 만든다.

따라서, "숫자를 많이 사는 것"을 1순위로, "높은 숫자를 사는 것"을 2순위로 두고 구매한다.

 

아래 코드에서 vector<int> dp[n] 은 금액 n으로 구매할 수 있는 가장 높은 수를 의미한다.

(높은 수의 기준은 위 우선순위를 따름)

금액 n으로 최대한 많이, 높게 구매한 숫자들을 vector 형태로 담아두고 있다.

결국 마지막에 구매한 숫자들을 이용해 높은 숫자를 만드는 것은 vector를 내림차순으로 정렬하는 것과 같으므로,

vector 형태로 저장해도 문제가 없다고 판단했다.

 

구매할 수 있는 숫자에 0이 존재할 때, 0만 구매하는 경우는 예외 처리를 해 주어야 한다.

단, 반드시 마지막 숫자를 산 뒤에 처리해 주어야 한다.

 

예시로, 10원의 금액으로 2원짜리 숫자 9와 1원짜리 숫자 0을 구매해 높은 수를 만들 때,

8원을 이용해 0 8개를 산 뒤, 마지막 2원으로 9를 구매해 900000000을 만드는 것이 제일 높은 수가 될 수 있기 때문이다. 즉, 수를 만드는 과정에서는 0만 구매한 것이 문제되지 않는다.

 

[코드]

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, budget;
int cost[10];
vector<int> dp[51];
 
bool compare(int b, vector<int> first, vector<int> second) {
    //마지막에 한 번만 확인) 어느 한 쪽의 모든 원소가 0이라면 폐기
    if (b == budget) {
        if (first.size() > 0 && first[first.size() - 1] == 0) return 0;
        if (second.size() > 0 && second[second.size() - 1] == 0) return 1;
    }
 
    //정렬되어 input으로 들어오는 두 vector를 비교해 큰 쪽을 알려줌 (0 : first, 1 : second)
    if (first.size() > second.size()) {
        //if (first[first.size() - 1] == 0) return 0;
        return 1;
    }
    if (first.size() < second.size()) {
        //if (second[second.size() - 1] == 0) return 1;
        return 0;
    }
 
    //사이즈가 같은 경우 제일 오른쪽 원소의 값을 비교
    int end = first.size() - 1;
    for (int i = end; i >= 0; i--) {
        if (first[i] > second[i]) return 1;
        if (first[i] < second[i]) return 0;
    }
    //같은 수일 경우 아무거나 반환
    return 0;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
 
    cin >> budget;
 
    for (int i = 1; i <= budget; i++) {
        for (int j = 0; j < n; j++) {
            //i원을 가지고 있는 상태에서 0 ~ n-1 숫자들을 각각 구매했을 때 비용을 비교한다.
            //1. 가격이 낮은 숫자를 우선으로 구매한다.
            //2. 같은 가격이면 높은 숫자를 구매한다.
 
            //현재 금액으로 숫자를 살 수 없는 경우
            if (i < cost[j]) continue;
 
            //현재 숫자(j)를 구매한 상태의 vector가 저장된 vector보다 크다면 교체
            vector<int> temp = dp[i - cost[j]];
            sort(temp.begin(), temp.end());
            temp.push_back(j);
            if (compare(i, temp, dp[i])) dp[i] = temp;
        }
        //현재 금액에서 아무것도 사지 않았을 경우를 체크
        if (compare(i, dp[i - 1], dp[i])) dp[i] = dp[i - 1];
    }
 
    if (dp[budget].empty()) dp[budget].push_back(0);
    for (int i = dp[budget].size() - 1; i >= 0; i--)
        printf("%d", dp[budget][i]);
 
    return 0;
}