15668-방 번호

15668-방 번호

아이디어성이 짙은 문제이다. 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) 까지의 숫자만이 나올 수 있는 고유한 조합이다.

#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;
}