수식을 조합해서 1~40을 만들 수 있는 수 찾기
이 문제는 작년에 조카의 수행평가 관련해서 질문 받은 것인데, 네 개의 서로 다른 숫자와 기본연산자를 조합하여 1~40의 모든 정수를 만들 수 있는 숫자를 찾는 문제였다. 사실 이 문제가 코딩 문제가 아닌 수학 수행 평가라는 점에서 눈을 의심하지 않을 수 없는데, 4개의 숫자로 구성되는 순열(24개)에 대해서, 각 숫자 사이에 들어갈 수 있는 연산자의 경우는 중복을 허용하여 5가지 (사칙연산에 필요한 4개와 연산자를 쓰지 않고 숫자를 붙이는 경우 1개 더)이기 때문에, 숫자 4개가 결정되었을 때 만들 수 있는 식의 개수는 무려 3,000 개이다. 1~9의 9개 숫자 중에서 4개를 선택하는 경우는 126가지이므로 4개의 숫자를 사용해서 만들 수 있는 식의 경우는 총378,000 가지이고, 이 문제는 전수 검사 (운이 좋다면 중간에 40가지의 수를 만드는 식을 만들 수 있는 조합을 찾을 수 있겠지만)를 통해서 찾아야 하는 수 밖에 없고, 결국 가능한 경우를 찾으려면 최악의 경우 거의 38만개의 식을 검사해야 하는데 이걸 컴퓨터의 힘을 빌리지 않고 수행평가를 하라는 것인지 이해가 가지 않았기 때문이다.
컴퓨터를 사용해서 이 문제를 해결하는 방법 자체는 간단한데, 의외로 실행 시간이 오래 걸릴 수는 있다. 이 문제에서는 어떻게든 숫자 4개의 조합에서 1~40까지를 만들 수 있는 경우를 찾으면 바로 종료하여 최대한 시간을 단축하는 방법을 사용했다.
접근방법
먼저 4개의 숫자와 사칙연산 연산자로 수식을 만드는 방법을 생각해보자. 4개의 숫자에는 연산자가 들어갈 수 있는 자리가 3개 있다. (맨앞에 -가 오는 경우도 포함시킬 수 있는데, 일단 여기서는 제외하고 생각한다.) 이 3개의 자리에 대해서 각 자리에는 4개의 연산자 중 하나 혹은 빈 문자열이 올 수 있다. 가능한 모든 조합으로 숫자와 연산자의 리스트를 만들고 이를 join() 해서 수식을 만들 수 있다. 만들어진 수식은 간단하게 eval() 함수를 사용해서 평가하는 것으로 한다.
4개의 숫자는 고정된 것이 아니라 순서를 바꿔가면서 검사하도록 한다. (순서까지 고정된 조합에서 연산자만 변경해서는 1~40 범위의 값을 모두 만드는 솔루션이 존재하지 않는다.)
검사하려는 값 중에서 정수가 아니거나, 지정된 범위 (1…40)을 벗어나는 경우를 제외한다. 추후에 확인을 위해서 계산 결과와 수식을 짝지어서 내놓는 제너레이터를 작성할 것이다. 제너레이터의 코드는 아래와 같다.1참고로 여기서 나눗셈 기호 문자(÷)는 vim에서 digraph로 입력했다. 입력 모드에서 <C-k>:- 를 순서대로 누르면 된다.
from itertools import product, permutations, combinations
def generate_expr(nums: tuple(str)):
ops = [''] + list('+-*/')
for ns in permutations(nums, 4):
for op in product(ops, repeat=3):
temp = [None] * 7
temp[::2] = ns
temp[1::2] = op
expr = ''.join(temp)
val = eval(expr)
if val == int(val) and 0 < val <= 40:
text = expr.replace('*', '×').replace('/', '÷')
yield (int(val), text)이제 위 제너레이터를 숫자 4개의 조합으로 호출하면, 해당 숫자로 만들 수 있는 1~40 사이의 값을 만드는 모든 수식을 얻을 수 있다. 그러면 각 조합에 대해서 위 제너레이터를 통해서 수식을 체크하고 1~40 사이의 값에서 빠짐없이 값을 얻을 수 있는지 체크한다. 결과의 수식을 표시하기 위해서 결과는 사전에 담아 체크하도록 했다.
def main():
for digits in combinations("1234567890", 4):
result = dict(zip(range(1, 41), [None] * 40))
for v, expr in generate_expr(digits):
result[v] = expr
if all(v is not None for v in result.values()):
for k, v in result.items():
print(f"{v} = {k}")
# 첫 결과를 출력한 후에 바로 종료
result
if __name__ = "__main__":
main()가능한 조합은 (2, 3, 4, 6)이며, 찾아낸 식은 다음과 같다. 참고로 전수 검사를 했을 때 가능한 숫자 조합은 하나가 더 있었다. (실제로 전수조사를 해도 그리 시간이 오래 걸리지는 않는다.)
1 = 6÷4÷3×2
2 = 64÷32
3 = 6÷4+3÷2
4 = 6×4÷3÷2
5 = 6+4-3-2
6 = 6×4÷3-2
7 = 6-4+3+2
8 = 6-4+3×2
9 = 6÷4×3×2
10 = 6×4÷3+2
11 = 6+4+3-2
12 = 6+4×3÷2
13 = 6×3÷2+4
14 = 6+32÷4
15 = 6+4+3+2
16 = 6×4÷3×2
17 = 6+4×2+3
18 = 6×4-3×2
19 = 6×4-3-2
20 = 6+4×3+2
21 = 63-42
22 = 4+36÷2
23 = 6×4-3+2
24 = 6×3+4+2
25 = 6×4+3-2
26 = 6×3+4×2
27 = 6-3+24
28 = 62-34
29 = 6×4+3+2
30 = 6×4+3×2
31 = 43-6×2
32 = 64-32
33 = 6+4+23
34 = 6-4+32
35 = 64÷2+3
36 = 6×4×3÷2
37 = 6÷2+34
38 = 6+34-2
39 = 63-24
40 = 6×3×2+4
