[programmers] N으로 표현 python

[프로그래머스] N으로 표현

문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

풀이과정

DP에 확실히 약한 것 같다.

풀이과정은 참고한 구르미의 개발 이야기, N으로 표현 을 참고하면 아주 자세한 풀이과정이 나와있으니 참고하면 좋을 것 같다. 나는 이 문제를 해결하지 못해서 소스코드도 해당 블로그를 참고했다.😥

소스코드

def solution(N, number):
    if N == number:
        return 1

    s = [set() for x in range(8)]
    for i, x in enumerate(s, start=1):
        x.add(int(str(N) * i))
    print(s)

    for i in range(1, 8): #s = [{5}, {55}, {555} .. ]
        for j in range(i):
            for op1 in s[j]: #s[j] = {5} 와 같은 것
                for op2 in s[i - j - 1]: #i개에 따라 만들 수 있는 것이기 때문에, i-1개까지로 만들 수 있는 것들과 연산한다., 또한 역연산을 가능하게 하기 위해서 1-3 2-2 3-1과 같이!
                    s[i].add(op1 + op2) #s[i] 인 이유: i에 따라 만들 수 있는 값 ex) i = 2 면 5 2개로 만들 수 있는 값
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        if number in s[i]:
            answer = i + 1
            break

    else:
        answer = -1

    return answer