1부터 9 사이에 연산자를 넣어 100 만들기

1 2 3 4 5 6 7 8 9 순서를 유지한 채 사이사이에 +, - 를 넣거나 아무것도 넣지 않고(붙여서 한 수로 만들고) 결과가 100이 되는 식을 모두 찾는 문제다.

빈칸이 8개고 각 칸에 세 가지가 들어가므로 3의 8제곱, 6561가지다. 전부 만들어서 계산해도 된다.

리스트를 고쳤다 되돌리는 방식

li = [str(i) for i in range(1, 10)]
type = ['', '+', '-']
cnt = 0

def do(n, equation):
    if n == 8:
        final = ''.join(equation)
        if eval(final) == 100:
            global cnt
            cnt += 1
            print(f'{final}')
        return

    for i in type:
        blob = equation.copy()
        equation[n] += i
        do(n + 1, equation)
        equation = blob

do(0, li)

숫자 리스트를 들고 다니면서 n 번째 원소 뒤에 연산자를 이어붙인다. 다음 후보를 시도하기 전에 원래대로 되돌려야 하므로 매번 copy() 로 스냅샷을 떠두고 재귀가 끝나면 그걸로 되돌린다.

돌아가긴 하는데 복사와 복원이 눈에 거슬렸다. 리스트를 공유하면서 고쳐 쓰기 때문에 생긴 일이다.

문자열을 넘기는 방식

def do(n=2, equation='1'):
    if n == 10:
        if eval(equation) == 100:
            eq.append(equation)
        return

    for i in op:
        do(n + 1, equation + i + str(n))

op = ['+', '-', '']
eq = []
do()

equation + i + str(n) 이 새 문자열을 만들어 넘긴다. 문자열은 고칠 수 없으니 호출한 쪽의 값은 그대로다. 복사도 복원도 필요 없어진다.

1 을 들고 시작해서 n 이 2부터 9까지 가며 연산자와 숫자를 한 쌍씩 붙인다. 앞의 것과 자리 세는 방식만 다르고 만드는 대상은 같다.

eval에 판정을 떠넘긴 것

두 버전 모두 eval 로 값을 구한다. 만들어진 문자열이 곧 파이썬 식이라 그대로 넘기면 된다.

12+34 처럼 붙여 쓴 숫자를 직접 파싱하려면 자릿수를 세어 합쳐야 하는데, 연산자를 안 넣는 선택지가 있는 이 문제에서는 그게 은근히 번거롭다. 만들 때 문자열로 만들었으니 계산도 문자열로 넘긴 셈이다.