백준) 15668 방 번호

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

0 ~ 9 까지 숫자 카드 스티커들을 한 번씩만 사용해 n = a + b 의 a와 b를 만들어야 한다.

여러 풀이 중에 내 생각에 제일 기똥찬 풀이는,

a와 b중에 작은 수를 b라고 하면, b의 가능 범위가 작아지므로, 완탐으로 때릴 수 있다는 것이다.

b에 스티커 5장을 쓰면 a도 5장이 되므로 b엔 최대 5장까지만 쓸 수 있다.

또한 b의 맨 앞자리는 끽 해야 8이므로, 1~87654가 b의 가능범위이다.

b가 정해지면 a도 정해지므로, 구만번 만에 풀리는 문제.

#include <bits/stdc++.h>
using namespace std;
 
int n;
 
bool func(int x, int& st) {
    while (x) {
        int tmp = (1 << (x % 10));
        if (st & tmp)
            return false;
 
        st |= tmp;
        x /= 10;
    }
 
    return true;
}
 
int main() {
    cin >> n;
 
    for (int i = 1; i <= 87654 && i < n; ++i) {
        int used = 0;
 
        if (!func(i, used))
            continue;
        if (!func(n - i, used))
            continue;
 
        cout << n - i << " + " << i;
        return 0;
    }
 
    cout << -1;
}