[백준 1082] 방 번호 [C]

백준 - 1082

---

풀이

가장 큰 방 번호는 만들어 질 수 있는 가장 긴 방 번호와 작거나 같다..

따라서, 가격이 가장 저렴한 방 번호로 가장 긴 번호를 만들고, 번호의 앞자리 부터 남은 M을 이용해 가능한 큰 수로 바꾸어 주면된다.

단, 앞자리에 0이 올 수 있는 경우는 방 번호가 0인 경우만 가능하므로 M이 작아 9~1의 번호로 교체가 불가능해 여전히 0이라면, 교체가 가능할 때까지 min만큼 다시 M에 더해주어야 한다.

---

소스코드

#include <stdio.h>
int main(){
    int N, M;
    scanf("%d", &N);
    int price[N], min = 50, idx;
    for (int i = 0; i < N; i++){
        scanf("%d", &price[i]);
        if (min >= price[i]){
            min = price[i];
            idx = i;
        }
    }
    scanf("%d", &M);
	
    int size = M/min;
    char num[51] = {0,};
    for (int i = 0; i < size; i++)
        num[i] = idx + '0';
    M %= min, idx = 0;
	
    for (int i = 0; i < size; i++){
        for (int j = N-1; j >= 0; j--)
            if (price[j] - min <= M){
                num[i] = j + '0';
                M -= (price[j]-min);
                break;
            }
			
        if (num[idx] == '0'){
            M += min;
            idx++;
        }
    }
    puts(idx == size ? "0" : num + idx);
}

---

출처

1082번: 방 번호