[PE] Project Euler 93

프로젝트 오일러 93번은 서로 다른 한 자리 숫자 4개가 주어졌을 때, 사이에 +, -, *, /, (, )를 적당히 끼워넣은 뒤 계산했을 때 나올 수 있는 숫자들을 전부 구한 다음, 그 안에 1부터 n 사이의 모든 숫자가 있다고 말할 수 있는 최대 n을 구하는 문제다. 예를 들어, 나올 수 있는 숫자들을 작은 순서대로 나열했을 때 1, 2, ..., 28, 30, ... 이런 리스트가 나온다면, 29를 만드는 방법이 없고 그보다 작은 자연수들은 모두 표현 가능하므로 답은 28.

 

계산식을 string으로 만든 뒤 이를 계산해주는 방법과, 숫자들의 순서, 사칙연산 기호의 순서를 조합해주는 방법을 알고 있으면 잘 활용해서 풀 수 있는 문제다. 아래의 두 글에 나온 함수들만 안다면 쉽게 풀 수 있을 것이다.

2020/09/30 - [언어 공부 기록/python] - [python] eval()함수에 대하여

2020/10/01 - [언어 공부 기록/python] - [python] product, permutations, combinations 함수에 대하여

 

from itertools import product, permutations, combinations
 
def calc_result(a, b, c, d, x1, x2, x3):
    fres = []
    kmb = permutations([a,b,c,d],4)
    for k in kmb: 
        a, b, c, d = k
        l = [
            f'{a}{x1}{b}{x2}{c}{x3}{d}',
            f'({a}{x1}{b}){x2}{c}{x3}{d}',
            f'{a}{x1}({b}{x2}{c}){x3}{d}',
            f'{a}{x1}{b}{x2}({c}{x3}{d})',
            f'({a}{x1}{b}){x2}({c}{x3}{d})',
            f'({a}{x1}{b}{x2}{c}){x3}{d}',
            f'(({a}{x1}{b}){x2}{c}){x3}{d}',
            f'({a}{x1}({b}{x2}{c})){x3}{d}',
            f'{a}{x1}({b}{x2}{c}{x3}{d})',
            f'{a}{x1}(({b}{x2}{c}){x3}{d})',
            f'{a}{x1}({b}{x2}({c}{x3}{d}))',
        ]
        res = []
        for x in l:
            try:
                v = eval(x)
                if v>0 and v//1 == v:
                    res.append(int(v))
            except: # 혹시나 0으로 나누는 일이 생기면 무시하고 넘어간다.
                pass
        fres+=res
    return sorted(list(set(fres)))
 
def obtained_till(l):
    res = -1
    for i in range(len(l)):
        if l[i]!=i+1:
            return i
    return res
 
x = ['+','-','*','/']
maxres = 0
answer = ''
for a, b, c, d in combinations(range(1,10),4):
    sol = []
    for x1, x2, x3 in product(x, repeat=3):
        sol+=calc_result(a, b, c, d, x1, x2, x3)
    val = obtained_till(sorted(list(set(sol))))
    if val>maxres:
        maxres = val
        answer = ''.join([str(i) for i in [a, b, c, d]])
    print([a, b, c, d], val)
 
print(maxres)
print(answer)

서로 다른 4개의 한자리 자연수를 뽑기 위해 combination을, 사칙연산 기호들의 조합을 뽑기 위해 product를, 서로 다른 4자리 자연수를 가지고 순서대로 배치할 수 있는 모든 안을 뽑기 위해 permutation을 활용한 것을 볼 수 있다. 이때 주의해야 할 것은, 혹시 0으로 나누는 경우가 생겼을 때 이를 잘 예외처리해주는 것.