1082번: 방 번호

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


$O(tn)$

직관적으로 자리수가 가장 많아야하고 그 다음엔 앞자리부터 큰 수가 와야함을 알 수 있다.
일단 비용이 작은 수로 자리 수를 최대한 길게 구성한다음,
앞 자리부터 가능한 큰 수로 바꾸는 작업을 하자.
한 가지 고려해야 할 사항은 모든 자리가 0으로 이루어지는 경우인데,
큰 수로 바꾸는 작업 중에 최고자리 수가 0인 경우에만 계속해서 다른 수로 대체가 가능한지 여부를 확인하고
모든 자리 수가 0이 아닌 다른 수로 대체가 불가능한 경우에만 0을 출력하면 된다.

#include<stdio.h>
int n, c[10], p;
char r[51];
int main() {
    while (scanf("%d", &n) != -1) {
        int m = 50, idx, s = 0, rcnt = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", c + i);
            if (m >= c[i]) m = c[i], idx = i;
        }
        scanf("%d", &p);
        for (; p >= m;) r[rcnt++] = idx + '0', p -= m;
        for (int i = 0; i < rcnt; i++) {
            for (int j = n - 1; j >= 0; j--)
                if (c[j] <= p + m) { r[i] = j + '0'; p += m - c[j]; break; }
            if (r[s] == '0') s++, p += m;
        }
        puts(s == rcnt ? "0" : r + s);
    }
    return 0;
}