[BOJ 14381] 숫자세는 양 (Small)

난이도

체감 난이도: Silver IV + 0.1

 

태그

• Simulation (시뮬레이션)
• Brute Force (브루트 포스)

 

풀이

1. 불가능한 경우는?

예제에도 나와있듯이, 0은 불가능합니다.

그런데 다른 수는 어떨까요?

 

큰 수를 생각해보면, 최대 200씩만 더하다 보면 언젠가는 1000????, 2000????, ..., 9000???? 같은 게 나올 테니

0을 제외하고는 항상 가능함을 알 수 있습니다.

 

2. 나머지 경우는?

사실 그렇게 크게 가지 않아도 됩니다.

어떤 수의 길이가 L이라면, (1번)과 같은 패턴이 L+1번째 숫자에서부터 나타나게 됩니다.

 

예로, 187을 보면

187, 374, 561, ..., 1122, 1309, ..., 2057, ..., 3179, ..., 9163, ..., 10098, ...

의 방식으로 나타나게 됩니다.

 

크게 잡아봐야 앞에 2자리가 더 붙는 정도니, 100번 정도 돌아가면 끝난다고 생각해볼 수 있습니다.

 

코드

bool chk[10];
 
void Main(){
    int t; cin >> t;
    for (int tt = 1; tt <= t; tt++){
        cout << "Case #" << tt << ": ";
        int x; cin >> x;
        if (x == 0){ cout << "INSOMNIA" << endl; continue; }
        int cnt = 0;
        memset(chk, 0, sizeof(chk));
        for (int ans = 1; ; ans++){
            int a = x*ans; //cout << a << ' ';
            while (a){ if (!chk[a%10]){ cnt += 1; } chk[a%10] = 1; a /= 10; }
            if (cnt == 10){ cout << x*ans << endl; break; }
        }
    }
}