83. 복면산

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

풀이 

- SEND에 있는 4자리 숫자 

- MORE에 있는 4자리 숫자

- 두 수를 더해서 5자리 숫자인 MONEY를 만족하는 순열을 찾는다.

- 주의해야할 점은 a[2]와 a[6]이 0이면 4자리 수를 만족하지 않기 때문에 이를 체크해서 return 시켜야 한다.

- 순열 구할때와 같이 for문을 사용해서 0-9까지 탐색한다.

=> 체크되지 않았을 시 a[L]에 i값을 넣고 ch[i]=1로 만든 후 DFS(L+1)로 진행

=> 계속해서 사용하지 않은 수들로만 순열을 이루게 한다.

 

 

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int a[10], ch[10];
//83. 복면산
//DEMNORSY 순서대로
int send(){
    //S=6 E=1 N=3 D=0
    return a[6]*1000+a[1]*100+a[3]*10+a[0];
}
int more(){
    //M=2 O=4 R=5 E=1
    return a[2]*1000+a[4]*100+a[5]*10+a[1];
}
int money(){
    //M=2 O=4 N=3 E=1 Y=7
    return a[2]*10000+a[4]*1000+a[3]*100+a[1]*10+a[7];
}

void DFS(int L){
    if(L==8){
        if(send()+more()==money()){
            if(a[6]==0 || a[2]==0) return;
            printf("  %d %d %d %d\n", a[6],a[1],a[3],a[0]);
            printf("+ %d %d %d %d\n", a[2],a[4],a[5],a[1]);
            printf("--------------\n");
            printf("%d %d %d %d %d\n", a[2],a[4],a[3],a[1],a[7]);
        }
    }else{
        for(int i=0;i<10;i++){
            if(ch[i]==0){
                a[L]=i;
                ch[i]=1;
                DFS(L+1);
                ch[i]=0;
            }
        }
    }
}


int main(){
    DFS(0);
    return 0;
}