티스토리 뷰
아이디어성이 짙은 문제이다. N=10억이기 때문에 당연히 전탐색은 불가능하다. 그래서 반드시 N을 다 보지 않고도 풀 수 있는 방법이 있을 것이라고 생각했다. 풀이를 말로 설명하기는 참 어려운 문제이다.
결론부터 얘기하자면, 단 43210까지만 봐도 모든 경우를 처리할 수 있다. i=1~43210까지의 반복문에서 i와 N-i 의 값을 구해서 그 두 값에서 겹치는 수가 있는지만 확인해주면 된다.
예를 들어, N=100 일 때를 생각해보자. i=1 때는 N-i(=k라고 하자)=99가 되고 k 자체에서 9가 두 번 사용되므로 탈락이다. i=2 때는 k=98이고 모든 수가 한 번 씩만 사용되었으므로 가능하다. 그래서 i=1~43210까지 하나라도 가능한 케이스가 있다면 출력하고, 모두 불가능하다면 답은 NO이다. 그렇다면 왜 이것이 유효한 풀이일까? 전탐색을 돌지도 않음에도 말이다. 이유는 딱 43210과 (i-43210) 까지만 답으로서 유효한 후보가 될 수 있기 때문이다. 543210이 아닌 이유는, 남은 숫자로 만들 수 있는 9,8,7,6 으로 이미 걸러진다. 43210 + 98765 = (141975) 까지의 숫자만이 나올 수 있는 고유한 조합이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include<stdio.h> #include<vector> using namespace std; int n; vector<int> int_seperation(int num){ int scale=1; vector<int> result; for( ; scale*10<=num ; scale*=10); for(int i=num ; scale ; scale/=10){ int cur=i/scale; result.push_back(cur); i=i-scale*cur; } return result; } int main(){ scanf("%d",&n); for(int i=1 ; i<=43210 ; i++){ bool used[10]={false}; int a=i,b=n-i,ans=0; if(a<=0 || b<=0) continue; vector<int> result=int_seperation(a); for(int here:result){ if(used[here]){ ans=-1; break; } else{ used[here]=true; } } result=int_seperation(b); for(int here:result){ if(used[here]){ ans=-1; break; } else{ used[here]=true; } } if(ans==0){ printf("%d + %d\n",a,b); return 0; } } printf("-1\n"); return 0; } | cs |
'Problem Solving > Etc.' 카테고리의 다른 글
[Codeforces 1065C] Make It Equal (0) | 2019.03.08 |
---|---|
[Codeforces 1118B] Tanya and Candies (Prefix Sum,부분합) (0) | 2019.02.21 |
15460-My Cow Ate My Homework(Silver) (0) | 2018.12.12 |
15465-Milk Measurement(Bronze)(set) (0) | 2018.12.12 |
15464-The Bovine Shuffle(Bronze) (0) | 2018.12.12 |