[백준] 1082번 : 방 번호 (C++)

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

 

문제

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 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원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

제한

• 1 ≤ N ≤ 10
• 1 ≤ Pi ≤ 50
• 1 ≤ M ≤ 50
• N, Pi, M은 정수

예제 입력 1 

3
6 7 8
21

예제 출력 1 

210

예제 입력 2 

3
5 23 24
30

예제 출력 2 

20

예제 입력 3 

4
1 5 3 2
1

예제 출력 3 

0

 

예제 입력 4 

10
1 1 1 1 1 1 1 1 1 1
50

예제 출력 4 

99999999999999999999999999999999999999999999999999

---

 

처음에는 Knapsack처럼 dp로 풀이를 하려했다. 그런데 생각해보니 그냥 최대한 긴 숫자를 뱉어내면 최대 값을 찾을 수 있는 문제였다.

 

1. 최대 자리수를 구하기 위해 가격이 싼순으로 정렬하고 첫째 자리가 0인경우를 제외하고 가장 싼 숫자를 최대한 산다.

 

2. 산 숫자를 내림차순으로 정렬하여 가지고 있는 숫자로 만들 수 있는 가장 큰 수를 만든다.

 

3. 이때 돈이 남고 더 큰 값의 숫자를 살 수 있는 여건이 된다면 가장 큰 자릿수부터 숫자를 바꾼다.

 

예제 1을 기반으로 설명을 해보자

0:6 1:7 2:8의 가격이 매겨져 있고, 현재 보유한 돈은 21원이다. 이때 첫자리가 0이 아닌 선에서 가장 싼 숫자를 사재기 한다면 100이라는 숫자를 얻을 수 있다. 1은 0을제외한 숫자 중 가장 싼 가격이며, 두번째, 세번째 자리에 들어오는 0은 가장 싼 숫자이기 때문이다.

 

그러나 100은 최대 자리수는 보장되지만 최대 숫자임은 보장되지 않는다. 따라서 가장 큰자리수부터 남은 잔액으로 숫자를 교체할 수 있으면 교체하는 작업을 할 것이다.

 

100을 사고 남은 돈 m'은 2이다(21-7-6-6). 각 자리 수를 n-1부터 순회하면서 비교해보면 1은 2로 교체될 수 있다. 

m + 1의가격 - 2의가격을 해도 0보다 크기 때문

 

이과정을 각 자리숫자마다 적용하면 210을 얻을 수 있다.

---

 

처음에

 if(P.size()>1 && P[1].second <= m){

            v.push_back(P[1].first);

            m-=P[1].second;

 

        }

에서 P.size() >1조건을 빼먹었더니 96%에서 계속 실패를 했다. N이 1일 경우에는 P[1]에 쓰레기값이 저장되어 있을 수 있기에 조건을 달아 P[1]을 선언했을때에만 연산이 되게 방지해야한다.

#include<bits/stdc++.h>

using namespace std;

int n,m;

vector <pair<int, int>> P;

vector <int> copy_P;

bool compare(pair<int, int> a, pair<int, int> b){

    if(a.second == b.second){

        return a.first > b.first;

    }

    return a.second < b.second;

}

bool compare2(int a, int b){

    return a>b;

}

void sol(int m){

    vector <int> v;

    if(P[0].first==0){

        if(P.size()>1 && P[1].second <= m){

            v.push_back(P[1].first);

            m-=P[1].second;

        }

        else{

            cout<<0;

            return;

        }

    }

    for(int i = 0 ; i < n ; i++){

        if(m>= P[i].second){

            int q = m/P[i].second;

            m %= P[i].second;

            for(int j = 0 ; j < q ; j++) v.push_back(P[i].first);

        }

    }

    sort(v.begin(), v.end(), compare2);

    for(int i = 0 ; i < v.size() ; i++){

        for(int j = n-1 ; j>0 ; j--){

            if(v[i]<j && m+copy_P[v[i]]-copy_P[j]>=0){

                m = m + copy_P[v[i]]-copy_P[j];

                v[i] = j;

                break;

            }

        }

    }

    for(int i = 0 ; i <v.size() ; i++){

        cout<<v[i];

    }

}

int main(void){

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin>>n;

    //숫자 : 가격순으로 저장

    for(int i = 0 ; i < n ; i++){

        int p; cin>>p;

        P.push_back({i, p});

        copy_P.push_back(p);

    }

    sort(P.begin(), P.end(), compare);

    cin>>m;

    sol(m);

}