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

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

 

방 번호는 무한으로 살 수 있으므로 N = 10이고 최대 값은 50이다. 이 때 모든 경우의 수를 다 해보는 것은 약 10^10으로 10억이상으로 엄청난시간이 걸린다.

 

중요한 추론은 숫자를 가장 길게 만들어야한다는 것이다.

 

그리고 91111 보다는 92000이 크고 100000이 더 크다.

 

즉 가장 비용이 적은 것들을 사용해서 먼저 가장 긴 방번호를 만들어둔 후 각 자리수마다 하나씩 비교하며 더 큰 값을 사용할 수 있을지 검사한다. 이 방법은 N^3 의 시간밖에 소요되지 않는다. 

 

그리고 각 번호의 개수를 배열에 저장해두고 큰 값부터 다음 값이 가능한지 확인한다. 

왜 큰 값부터 해야하냐면 만약 작은것부터 시행했을 때는 다음과 같은 문제가 발생한다.

 

3

6 7 8

22

 

1. 가장 작은 길이 : 100 (6 + 6 + 7 = 21) 남은 돈 = 2

2. 0부터 더 큰 값이 되는지 확인하면 0번 1개를 2번으로, 0번 1개는 1번으로 바꿀 수 있음. (7 + 7 + 8 = 22) 남은돈 = 0

3. 1번은 2번으로 갈 수 없음. 1번을 사지않는다고 처도 2번을 살 수 없기 때문

 

즉, 모든 돈을 써버리는 최적의 값이 되어야할 순간에 211이 먼저 도달해버린다.

그러나 만약 큰 수부터 해보면

 

1. 가장 작은 길이 : 100 (6 + 6 + 7 = 21) 남은 돈 = 2

2. 2번은 이미 제일 크므로 제외

3. 1번을 2번으로 바꿀 수 있음 (6 + 6 + 8 = 22) 남은 돈 = 1

4. 0번 1개를 2번으로 바꿀 수 있음 (6 + 8 + 8) 남은 돈 = 0

 

여기서는 정답으로 220을 도출할 수 있다.

 

2 1 1 

2 2 0 

 

두개의 조합의 가격이 같기 때문에 일어난 일이다. 같은 조합 중 최댓값을 얻기 위해서는 큰 값이 먼저 나오도록 해야한다. 

 

Greedy가 가능한 이유? 

1. 부분최적해를 갖추고 있다.

 

1 2 3 4 에서 3 4 만 가져와도 같은 로직을 가진다.

 

2. 탐욕선택조건을 만족한다.

 

뭘 선택하더라도 계속 최적의 값만을 쫓아 움직인다. 이전에 뽑았던 것을 버리고 새로운 것을 취할 뿐이지 3번에서 최적의 해를 찾다가 갑자기 0번을 버리지 않는다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int cnt[11];

vector<int> arr;

int main(){
    int N; cin >> N;
    int idx = -1;
    int minValue = 51;
    for(int i = 0; i < N; i++){
        int tmp; cin >> tmp;

        arr.push_back(tmp);
        if(i != 0){
            if(minValue > tmp){
                minValue = tmp;
                idx = i;
            }
        }
    }

    int M; cin >> M;

    if(minValue > M) {
        cout << 0 << '\n';
        return 0;
    }

    if(arr[0] < minValue){
        cnt[idx] = 1;
        cnt[0] = (M - minValue) / arr[0];

        M -= (arr[idx] * cnt[idx] + arr[0] * cnt[0]);
    }else{
        cnt[idx] = M / minValue;

        M -= cnt[idx] * arr[idx];
    }
    
    for(int i = N - 1; i > -1; i--){
        //cout << "돈:: " << M << " 현황 :: " << cnt[0] << ' ' << cnt[1] << ' ' << cnt[2] << ' ' << endl;
    
        if(cnt[i] != 0){
            int num = cnt[i];
            
            for (int k = 0; k < num; k++){
                int nextIdx = -1;
                int nextMoney = -1;
                for(int j = i + 1; j < N; j++){
                    int nowMoney = M + arr[i] - arr[j];
                   
                    if(nowMoney >= 0){
                        if(nextIdx < j){
                            nextIdx = j;
                            nextMoney = nowMoney;
                        }
                    }
                }
                if(nextIdx != -1){
                    cnt[i]--; 
                    cnt[nextIdx]++;
                    M = nextMoney;
                }
            }
        }
    }
    for(int i = N - 1; i > -1; i--){
        for(int j = 0; j < cnt[i]; j++){
            cout << i;
        }
    }
}