[코딩으로 풀어보기] 문제적 남자 4화 - (9, 9, 9, 9, 9, 9)으로 100 만들기

문제

이번 문제는 문제적남자 4화에 나온 뇌풀기문제이다.

6개의 9를 사용해서 100을 만드는 수식을 찾는 문제인데, DFS로 모든 경우의 수를 탐색하면 되는 전형적인 문제로 보인다.

숫자들 사이에 수식을 끼워 모든 경우의 수를 만들어보고, 파이썬의 eval 함수로 계산한 결과가 100 이 되는 경우만 세어보면 될 것 같다.

9와 사칙연산만 사용하기

6개의 9 사이마다 사칙연산을 끼워넣어서 100이 만들어지는 경우를 찾아본다. 4개의 연산자를 5개의 공간에 끼워넣으므로 경우의 수는 \(4^5 = 1024\) 가지밖에 되지 않는다.

정답은 12개로 생각보다 많은데, 이건 순열이 달라서 세어진 것이고 조합으로 보면 단 하나이다. (정답 아래에 적음)

정답

9+9+9/9+9*9 = 100.0
9+9+9*9+9/9 = 100.0
9+9/9+9+9*9 = 100.0
9+9/9+9*9+9 = 100.0
9+9*9+9+9/9 = 100.0
9+9*9+9/9+9 = 100.0
9/9+9+9+9*9 = 100.0
9/9+9+9*9+9 = 100.0
9/9+9*9+9+9 = 100.0
9*9+9+9+9/9 = 100.0
9*9+9+9/9+9 = 100.0
9*9+9/9+9+9 = 100.0

모두 아래의 수식과 같다.

\(9+9+\frac{9}{9}+9 \cdot 9\)

코드

num = [9,9,9,9,9,9]
op = ['+', '-', '/', '*']

def evaluate(os):
    eq = str(num[0])
    for i in range(len(os)):
        eq += str(os[i]) + str(num[i+1])
    return eq, eval(eq)

def dfs(os):
    s, val = evaluate(os)
    if len(os) >= 5:
        if val == 100:
            print(s, '=', val)
        return None
    for o in op:
        os.append(o)
        dfs(os)
        os.pop()

# Run
dfs([])

수 붙여쓰기를 포함한 결과

99+9+99/9 처럼 수를 붙여서 99를 만드는 것도 가능하다면, 결과는 더 많을 것이다.

위의 코드에서 바꿀 것은 사용하는 연산자 중에 공백을 넣는 일 밖에 없다. 

정답

앞서 확인했던 사칙연산만 사용한 12개의 케이스를 제외하면, 총 34개의 수식이 있지만, 조합만 보면 아래 4가지이다.

\( \begin{eqnarray} 100 &=& 9-9+\frac{9}{9}+99 \\ &=& \frac{9}{9} \cdot 99+\frac{9}{9} \\ &=& 99+\frac{ \frac{9}{9} }{9} \cdot 9 \\ &=& \frac{99}{99}+99 \end{eqnarray} \)

9+9/9+99-9 = 100.0
9/9+9-9+99 = 100.0
9/9+99*9/9 = 100.0
99/99+99 = 100.0
99+9/9+9-9 = 100.0
9/9/9*9+99 = 100.0
99-9+9+9/9 = 100.0
99*9/9+9/9 = 100.0
99-9+9/9+9 = 100.0
99+9-9+9/9 = 100.0
9/9*99+9/9 = 100.0
9+9/9-9+99 = 100.0
9-9+99+9/9 = 100.0
99+9/9/9*9 = 100.0
99+9/9*9/9 = 100.0
99/9*9+9/9 = 100.0
9+99-9+9/9 = 100.0
9/9-9+99+9 = 100.0
9/9-9+9+99 = 100.0
9/9+9/9*99 = 100.0
9/9+9+99-9 = 100.0
9/9+99+9-9 = 100.0
9*9/9/9+99 = 100.0
9+99+9/9-9 = 100.0
9-9+9/9+99 = 100.0
9/9+99/9*9 = 100.0
9*99/9+9/9 = 100.0
99+9/9-9+9 = 100.0
99+99/99 = 100.0
9/9*9/9+99 = 100.0
99+9+9/9-9 = 100.0
99+9*9/9/9 = 100.0
9/9+9*99/9 = 100.0
9/9+99-9+9 = 100.0

코드

num = [9,9,9,9,9,9]
op = ['+', '-', '/', '*', '']

def evaluate(os):
    eq = str(num[0])
    for i in range(len(os)):
        eq += str(os[i]) + str(num[i+1])
    return eq, eval(eq)

def dfs(os):
    s, val = evaluate(os)
    if len(os) >= 5:
        if val == 100:
            print(s, '=', val)
        return None
    for o in op:
        os.append(o)
        dfs(os)
        os.pop()

# Run
dfs([])

제곱까지 추가?

제곱(**)을 추가해서 실행해보면 스크립트가 엄청 오래 걸린다.
왜냐하면 만들어지는 수식 중에 엄청나게 큰 수가 계산되는 경우가 있기 때문이다. 예시로, "99**99**99" 와 같은 \(99^{99^{99}}\) 가 있다.

그래서 수식을 만드는 중간마다 수의 범위를 확인해서 너무 커진다면 탐색하지 않도록 해야하는데, 생각보다 공이 많이 들어가는 것 같아서 미뤘다. 시간이 생긴다면 코드를 업데이트할 예정이다.

직접 찾은 것으로는 이렇다.

\( \begin{eqnarray} 100 &=& 99^{\frac{9}{9}}+\frac{9}{9} \\ &=& 99+\frac{9^9}{9^9} \end{eqnarray} \)

이보다 더 멋있는 수식을 찾을 수 있다면 좋겠다.