83. 복면산 SEND+MORE=MONEY (MS 인터뷰) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <stdio.h>

int a[8];
int ch[10];

int Send()
{
	return a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
}

int More()
{
	return a[4] * 1000 + a[5] * 100 + a[6] * 10 + a[1];
}

int Money()
{
	return a[4] * 10000 + a[5] * 1000 + a[2] * 100 + a[1] * 10 + a[7];
}

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

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

1. SEND + MORE = MONEY 의 의미는 다음과 같다. MONEY의 알파벳을 보면 SEND의 EN과 MORE의 MO, 그리고 Y로 이루어진 단어이다.

즉 9 5 6 7 + 1 0 8 5 = 1 0 6 5 2 이다. 이런 규칙을 갖는 숫자를 찾는 코드를 작성하면 위와 같다.

 

2. 먼저 배열 a의 크기를 8로 한다. S, E, N, D, M, O, R, Y 알파벳에 해당하는 숫자만 있으면 되기 때문이다.(E는 겹치기 때문에 한 번만 있으면 된다)

• 배열 a

0

0

0

0

0

0

0

0

          ▲S                   ▲E                  ▲N                  ▲D                  ▲M                  ▲O                   ▲R                  ▲Y

 

idx 0부터 숫자 0~9까지 넣어가면서 위 규칙과 같은 숫자를 찾게 되면 출력하는 프로그램이다.