BOJ 1082 - 방번호

www.acmicpc.net/problem/1082

1082번: 방 번호

 

 

문제를 푸는 전반적인 아이디어는 이렇다

 

먼저 주어진 숫자에서,

첫번째 인덱스에서 부터 마지막번째 인덱스까지 가장 작은 수 first

두번째 인덱스에서 부터 마지막번째 인덱스까지 가장 작은 수 second 를 잡는다.

 

이 두 숫자를 잡아야 하는 이유는, 

 

첫번째로, 가능한 비용범위 내에서 최저값을 잡아내기 위함이다

(문자열로 일정한 틀을 잡아줘야 최댓값으로 갱신이 가능하기 때문임,

물론 이는 구현 방법에 따라서 개개인마다 차이가 있어서 꼭 이게 답이라고 할 수는 없는것 같다)

 

두번째로, 숫자를 만약 하나만 잡고 시도한다면 0만 여러개 나올 수도 있다.

0000 이나 0 이나 똑같기 때문이다. 

그래서 두번째로 작은 수를 잡아내면 0 이 아닌 다른 값을 초기 값으로 포함할 수 있기 때문이다.

예를들어 10, 200 등...

 

이 두 숫자를 잡아서 있는 돈만큼 자릿수를 늘려나간다.

(가장 큰 숫자를 만들어야 하기 때문에, 자릿수가 최대한 늘어나는게 좋으며, 자리수가 최대한 늘어날려면, 싼 값에 살 수 있는 숫자들로 채워넣었다가, 나중에 숫자가 높은것들로 채우면 된다)

 

초기화를 시킨 후 남은 돈에서

더 비싼 다른 높은 숫자로 바꿀 수 있는지 확인한다.

 

문제에서 숫자를 사는 비용이 작은 숫자 부터 주어진다고 했으므로

큰 숫자가 뒤에 있을것이기에, 뒤에부터 탐색을해서, 새로 갱신할 수 있는게 있는지 확인해준다.

 

 

- C++

#include <algorithm>
#include <iostream>
#include <string>
 
#define INF 987654321
 
using namespace std;
 
int N, money;
int arr[10];
string answer; 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    for (int i = 0; i < N; ++i) cin >> arr[i];
    
    cin >> money;
        
    int first = INF, second = INF;
    int first_idx, second_idx; 
    
    for (int i = 0; i < N; ++i) {
        if (arr[i] < first) {
            first = arr[i];
            first_idx = i;
        }
    }
    
    for (int i = 1; i < N; ++i) {
        if (arr[i] < second) {
            second = arr[i];
            second_idx = i;
        }
    }
    
    if (money < second) {
        cout << "0";
        return 0;
    }
    
    money -= second;
    answer.push_back('0' + second_idx);
    while(money >= first) {
        answer.push_back('0' + first_idx);
        money -= first;
    }
    
    int idx;
    
    for (int i = 0; i < answer.length(); ++i) {
        for (int j = N - 1; j >= 0; --j) {
            idx = answer[i] - '0';
                        
            if (money >= arr[j] - arr[idx]) { // 비용 뒤에서 부터 살수있으면  
                money -= (arr[j] - arr[idx]);
                answer[i] = '0' + j;
                break;
            }            
        }
    }
    
    cout << answer;
    
    return 0;
}

 

 

아이디어 참조

www.acmicpc.net/board/view/47793

글 읽기 - [1082]방 번호 힌트좀 주실 수 있으실까요?