관리 메뉴

Joonas' Note

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

개발/python

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

joonas 2022. 4. 2. 13:21

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

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

    문제

    문제는 간단하다. 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의 특성)

    반응형
    0 Comments
    댓글쓰기 폼