이 문제는 작년에 조카의 수행평가 관련해서 질문 받은 것인데, 네 개의 서로 다른 숫자와 기본연산자를 조합하여 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)을 벗어나는 경우를 제외한다. 추후에 확인을 위해서 계산 결과와 수식을 짝지어서 내놓는 제너레이터를 작성할 것이다. 제너레이터의 코드는 아래와 같다.
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