# [Gold IV] 방 번호 [문제 링크](https://www.acmicpc.net/problem/15668) ## 문제 설명 <p>택희는 이번에 이사를 했다. 택희의 이번 방 주소는 연세동 연세빌딩 N호이다. 택희는 방의 문 앞에 예쁜 스티커로 방 번호를 붙이려고 한다.</p> <p>하지만 문을 꾸미기 위해 스티커 세트를 사온 택희는 방 번호를 붙이려던 중 무언가 문제가 있음을 알아차렸다. 스티커 세트에는 0부터 9까지의 정수가 한 장씩만 들어있었는데, 택희의 방 번호에는 같은 자릿수가 두 개 이상 들어갈 수도 있으므로 정상적인 방법으로는 방 번호를 붙일 수가 없었다.</p> <p>이에 택희는 새로운 방법을 생각해냈다. N을 만드는 대신, 두 자연수 A와 B를 만들어 A+B=N이 되도록 하는 것이다. 단, 스티커 세트에는 0 이상 9 이하의 정수가 하나씩밖에 없어서, A와 B에 쓰인 모든 자릿수는 어떤 것도 두 번 이상 쓰여선 안 된다. 모양이 특이한 스티커이기 때문에, 6과 9를 서로 뒤집어서 쓰는 것 또한 불가능하다.</p> <p>예를 들어, 방 번호가 555호라고 하자. 이를 123 + 432로 분할할 경우, 2와 3이 총 두 번씩 쓰였으므로 불가능한 분할이다. 99 + 456으로 분할하는 것도 마찬가지로, 9가 두 번 쓰였으므로 불가능하다. 하지만 512 + 43으로 분할할 경우, 어떤 자릿수도 두 번 이상 쓰이지 않았으므로 가능한 분할이다.</p> <p>하지만 택희의 방 번호는 제법 큰 수여서 빠르게 A와 B를 찾아낼 수가 없었다.</p> <p>여러분이 한번 택희를 도와줘 보도록 하자.</p> ## 입력 <p>첫 줄에 방 번호 N이 주어진다. (1 ≤ N ≤ 10⁹)</p> ## 출력 <p>만일 조건을 만족하는 A와 B가 존재하지 않는다면 첫째 줄에 -1 하나만을 출력한다.</p> <p>답이 존재한다면, A + B = N이 되며 문제의 조건을 만족하는 두 자연수 A와 B를 출력 예제 1의 형식에 맞게 출력한다.</p> <p>만일 그런 A, B가 여러 가지라면 아무 쌍이나 하나만 출력한다.</p> ## 풀이 #### 백트래킹으로 A를 만들어서 해결하였다. 하지만 이 문제는 브루트포스로 N의 절반까지만 탐색을 했다면 더 빨리 풀 수 있었을 것이다. ``` c++ #include<bits/stdc++.h> using namespace std; int n; string s, res="-1"; int used[10]; bool finish; void chk(string a) { if(a.length()==10) return; int intA = stoi(a); if(n<=intA) return; string b = to_string(n-intA); bool ret=true; for(int i=0;i<b.length();i++) if(++used[b[i]-'0']==2) ret=false; for(int i=0;i<b.length();i++) --used[b[i]-'0']; if(ret) { res = a + " + " + b; finish=true; } } void dfs(string val="") { if(finish || val.length()>s.length()) return; if(val.length()) chk(val); for(int i=0;i<10;i++) { if(val.length()==0 && i==0) continue; if(!used[i]) { used[i]++; dfs(val+to_string(i)); used[i]--; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> s; n = stoi(s); dfs(); cout << res; } ```