[코딩으로 풀어보기] 문제적남자 107화 - 1부터 9까지의 숫자를 한 번씩 사용해서 올바른 식 만들기

우연히 발견해서 오랜만에 적어보는 코딩으로 풀어보기 게시글이다.

이번에는 코드 없이 풀어본 풀이도 있다.

문제

문제는 간단하다. 1부터 9까지의 숫자를 한 번씩만 사용해서, 수식이 올바르도록 비어있는 9개의 칸을 채우는 문제이다.

코딩 풀이

숫자를 한 번씩만 사용한다는 조건때문에, 전체 경우의 수를 탐색하면 \(9! = 362,880\)개 밖에 안된다.
그래서 모든 경우를 전탐색해도 여유롭게 풀만하다. 답을 찾는 데 10ms도 안 걸릴 것 같다.

코드

import itertools

numbers = [i for i in range(1, 10)]
count = 0

for p in itertools.permutations(numbers):
    a1, a2, a3 = p[:3]
    a4 = p[3] * 10 + p[4]
    b1, b2 = p[5:7]
    b3 = p[7] * 10 + p[8]
    if a1/a2+a3+a4 == b1/b2/b3:
        print(f'{a1}/{a2}+{a3}+{a4} = {b1}/{b2}+{b3}')
        count += 1

print(f'Total: {count}')

정답

총 121개의 정답이 나오는데, 너무 길어서 아래처럼 적겠다.

1/2+5+79 = 6/4+83
1/2+8+49 = 3/6+57
1/2+9+48 = 3/6+57
1/2+9+75 = 3/6+84
1/2+9+75 = 6/4+83
1/3+5+79 = 2/6+84
1/3+8+49 = 2/6+57
1/3+9+48 = 2/6+57
1/3+9+75 = 2/6+84
2/1+5+79 = 6/3+84
2/1+7+58 = 9/3+64
2/1+8+49 = 6/3+57
2/1+8+57 = 9/3+64
2/1+9+48 = 6/3+57
2/1+9+75 = 6/3+84
2/6+5+79 = 1/3+84
2/6+5+87 = 4/3+91
2/6+7+85 = 4/3+91
2/6+8+49 = 1/3+57
2/6+9+48 = 1/3+57
2/6+9+75 = 1/3+84
2/8+3+69 = 5/4+71
2/8+9+63 = 5/4+71
3/1+5+79 = 6/2+84
3/1+8+49 = 6/2+57
3/1+9+48 = 6/2+57
3/1+9+75 = 6/2+84
3/6+4+79 = 5/2+81
3/6+5+79 = 1/2+84
3/6+7+48 = 9/2+51
3/6+8+47 = 9/2+51
3/6+8+49 = 1/2+57
3/6+9+48 = 1/2+57
3/6+9+74 = 5/2+81
3/6+9+75 = 1/2+84
4/1+5+76 = 9/3+82
4/1+5+87 = 6/2+93
4/1+6+75 = 9/3+82
4/1+7+85 = 6/2+93
4/8+5+27 = 9/6+31
4/8+7+25 = 9/6+31
5/1+2+79 = 6/3+84
5/1+3+79 = 6/2+84
5/1+4+76 = 9/3+82
5/1+4+87 = 6/2+93
5/1+6+74 = 9/3+82
5/1+7+39 = 6/2+48
5/1+7+84 = 6/2+93
5/1+9+37 = 6/2+48
5/1+9+72 = 6/3+84
5/1+9+73 = 6/2+84
5/2+3+87 = 6/4+91
5/2+7+83 = 6/4+91
6/1+4+75 = 9/3+82
6/1+5+74 = 9/3+82
6/2+5+79 = 3/1+84
6/2+5+79 = 4/1+83
6/2+8+49 = 3/1+57
6/2+8+49 = 7/1+53
6/2+9+48 = 3/1+57
6/2+9+48 = 7/1+53
6/2+9+75 = 3/1+84
6/2+9+75 = 4/1+83
6/3+5+79 = 2/1+84
6/3+5+79 = 4/1+82
6/3+8+49 = 2/1+57
6/3+8+49 = 7/1+52
6/3+9+48 = 2/1+57
6/3+9+48 = 7/1+52
6/3+9+75 = 2/1+84
6/3+9+75 = 4/1+82
6/4+3+79 = 5/2+81
6/4+5+87 = 1/2+93
6/4+7+85 = 1/2+93
6/4+9+73 = 5/2+81
6/8+5+19 = 7/4+23
6/8+9+15 = 7/4+23
6/9+7+18 = 5/3+24
7/1+2+58 = 9/3+64
7/1+4+85 = 6/2+93
7/1+5+39 = 6/2+48
7/1+5+84 = 6/2+93
7/1+8+52 = 9/3+64
7/1+9+35 = 6/2+48
7/2+1+59 = 4/8+63
7/2+9+51 = 4/8+63
7/3+4+85 = 2/6+91
7/3+5+84 = 2/6+91
8/1+2+49 = 6/3+57
8/1+2+57 = 9/3+64
8/1+3+49 = 6/2+57
8/1+7+52 = 9/3+64
8/1+9+42 = 6/3+57
8/1+9+43 = 6/2+57
8/3+2+47 = 6/9+51
8/3+7+42 = 6/9+51
9/1+2+48 = 6/3+57
9/1+2+75 = 6/3+84
9/1+3+48 = 6/2+57
9/1+3+75 = 6/2+84
9/1+5+37 = 6/2+48
9/1+5+72 = 6/3+84
9/1+5+73 = 6/2+84
9/1+7+35 = 6/2+48
9/1+8+42 = 6/3+57
9/1+8+43 = 6/2+57
9/2+3+75 = 6/4+81
9/2+5+73 = 6/4+81
9/3+5+68 = 2/1+74
9/3+5+68 = 4/1+72
9/3+7+48 = 2/1+56
9/3+7+48 = 6/1+52
9/3+8+47 = 2/1+56
9/3+8+47 = 6/1+52
9/3+8+65 = 2/1+74
9/3+8+65 = 4/1+72
9/6+5+17 = 4/8+23
9/6+5+38 = 7/2+41
9/6+7+15 = 4/8+23
9/6+8+35 = 7/2+41
Total: 121

직접 풀이

왼쪽의 빈칸들을 (붙은 것은 하나의 수로 보고 묶어서) 순서대로 a1, a2, a3, a4, 오른쪽의 빈칸들을 b1, b2, b3 라고 하자.

그럼 수식은 a1/a2+a3+a4 = b1/b2+b3 인데, 소수점이 생기는 부분은 a1/a2, b1/b2 뿐이다.
둘을 기약분수로 만들어서 생기는 소수점만 맞추면 후보가 줄어든다.

예를 들어, a1/a2가 1/2 라면 좌변의 결과에 0.5가 있다는 뜻이고, 그럼 우변에도 0.5가 있어야한다. 소수점은 나눗셈으로밖에 만들어질 수 없기 때문에, b1/b2 에서 0.5가 나와야하고, 가능한 경우는 3/2, 2/4, 3/6, ... 이다.

문제를 풀기 위해 a1/a2를 고정해서 찾아본다. (답이 없을 수도 있음)

a1=1, a2=2 로 고정하면, 가능한 b1/b2은 3/6, 4/8 밖에 없고, 그럼 가능한 것은 아래처럼 2개의 수식이 나온다.

• 1/2+{a3}+{a4}=3/6+{b3} -> (1)
• 1/2+{a3}+{a4}=4/8+{b3} -> (2)

둘 중에 하나인데, (1)의 경우에는 4, 5, 7, 8, 9 만 이용해서 a3, a4, b3 를 만들어야한다. 이정도면 5! (120가지) 이니까 9! 보다는 훨씬 낫다.

a3	a4	b3	a3+b4==b3
4	57	89	no
4	57	98	no
4	58	79	no
4	58	97	no
4	75	89	no
4	75	98	no
...	...	...	...

막상 해보니 120개를 전부 찾기는 힘들어보인다.
여기부터는 운과 센스의 영역이라고 느껴지는데, 이어서 전개해보자.

식을 만족하기 위해서 a3+a4==b3 가 되려면 \(|a_4-b_3|\)가 \(a_3\)이 나와야한다. 그런 조합만 생각해보면 되는데, 숫자 4, 5, 7, 8, 9 로 만들 수 있는 조합 중에는 "5+79=84" 가 있다.
이 경우에는 9가 있고 남은 수가 4, 5, 7, 8로 1씩 차이나서 쉽게 만들 수 있었다. (숫자 9의 특성)