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

---

🔗 문제 링크

1082번: 방 번호

---

💡 문제 풀이 및 해석

1. 만약 0 만 살 수 있거나 N == 1인 경우 방번호는 0으로 고정이다.
2. 가장 큰 수는 어떤 수일까?
   2-1. 자릿수가 긴 수이다.
   2-2. 자릿수가 같다면, 앞에서부터 비교할 때, 앞자리의 수가 큰 수이다.
3. 먼저 0을 제외한 가장 코스트가 낮은 숫자를 찾아 맨 앞자리에 넣는다.
4. 0과 비교해서 더 낮은 코스트인 수를 뒤에 최대한 많이 붙인다.
5. 가장 앞자리부터 9 ~ 앞자리의수 까지 비교해서 교체할 수 있으면 교체한다.

---

⭐️ 정답 코드 및 설명

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

int N;
int budget;
vector<int> P;
void init() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int cost; cin >> cost;
        P.push_back(cost);
    }
    cin >> budget;
}

string sol() {

    if (N == 1) return "0";
    // 예산으로 살 수 있는 숫자가 없을 때(0을 제외한), 0을 반환
    for (int i = 1; i < N; i++) {
        if (budget >= P[i]) break;
        if (i == N - 1) return "0";
    }

    string answer = "";
    int minCost=999;
    string minNum;

    // 가장 코스트가 낮은 숫자를 구한다. 단, 같은 코스트면 큰 숫자를 선택.
    for (int i = N - 1; i > 0; i--) {
        if (P[i] < minCost) {
            minCost = P[i];
            minNum = i + '0';
        }
    }

    // 맨 앞자리에 배치
    answer += minNum;
    budget -= minCost;

    // 가장 코스트가 낮은 숫자를 뒤에 쭉~ 붙혀준다.
    if (P[0] < minCost) {
        minCost = P[0];
        minNum = "0";
        while (budget >= minCost) {
            budget -= minCost;
            answer += minNum;
        }
    }
    else {
        while (budget >= minCost) {
            budget -= minCost;
            answer += minNum;
        }
    }

    int index = 0;
    // 숫자 끝까지 보거나 예산이 남아있을 때까지 반복한다.
    while (answer.size() > index && budget > 0) {
        int num = answer[index] - '0';
        for (int i = N - 1; i > num; i--) { // 더 큰 앞자리로 바꿀 수 있나?
            if (budget >= (P[i] - P[num])) { // 예산이 교체비용보다 크다면
                answer[index] = i + '0'; // 교체
                budget -= (P[i] - P[num]);
                break;
            }
        }
        index++; // 다음 자릿수로 이동
    }

    return answer;
}

int main() {

    init();
    cout << sol();

}

---

🤔 문제 후기

문제의 풀이를 생각하는 것은 어렵지 않았다. 하지만, 구현하는 과정에서 숫자를 교체해야 하는데, 아래 코드 부분에서 budget >= (P[i] - P[num]) 부분이 있는데, 이 부분에 =을 붙이지 않아서 틀린 것과, break; 대신 실수로 continue;를 넣어 가장 큰 수로 교체하고 그 다음 큰 수로 교체해버리는 실수를 해버리고 말았다. (각종 테스트 케이스는 통과되어서 처음에 뭐가 문제인지 몰랐다.) 더 큰 수로 교체할 때, 교체비용이 발생하지 않을 수 있고, 중간에 빠져나와야 하는데 빠져나오지 못한 부분을 생각하지 못해서 시간이 생각보다 오래 걸렸다.

int index = 0;
    // 숫자 끝까지 보거나 예산이 남아있을 때까지 반복한다.
    while (answer.size() > index && budget > 0) {
        int num = answer[index] - '0';
        for (int i = N - 1; i > num; i--) { // 더 큰 앞자리로 바꿀 수 있나?
            if (budget >= (P[i] - P[num])) { // 예산이 교체비용보다 크다면
                answer[index] = i + '0'; // 교체
                budget -= (P[i] - P[num]);
                break;
            }
        }
        index++; // 다음 자릿수로 이동
    }