10610번: 30

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


$O(l)$

30=3*10인데 3의 배수 판정법에 따라 각 자리수 합이 3의 배수여야 하며, 10의 배수여야 하므로 끝 자리에는 0이 와야 한다.
주어진 수를 큰 한자리 수부터 배열해보자. 이것들의 합이 3의 배수가 아니라면 애초에 만들기가 불가능하며
한자리 수 중에 0이 있다면 완성된 수의 끝에는 무조건 0이 있기 때문에 없는 경우는 불가능하다.
두 조건을 모두 만족한다면 30의 배수이며 가장 큰 수가 된다.

#include<stdio.h>
int t, n[10];
int main() {
    for (int x; scanf("%1d", &x) != -1;) t += x, n[x]++;
    if (t % 3 || !n[0]) puts("-1");
    else for (int i = 9; i >= 0; i--) while (n[i]--) printf("%d", i);
    return 0;
}