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

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 함수를 작성하세요.

풀이

def solution(N, number):
    answer = -1
    dp = []
    
    for i in range(1, 9): # # i = N의 개수
        all_case = set()
        check_number = int(str(N) * i)
        # {N}, {NN} , {NNN}...
        all_case.add(check_number)
        print(all_case, "현재 all case 자릿수")
        for j in range(0, i - 1):# 0~ 7
            #이전까지 생성한 숫자 집합에 대해 하나씩 더하여 새로운 숫자 집합을 만들기
            print(j,dp, "마지막에 dp 삽입했다고")
            for op1 in dp[j]:# dp[0] =[5] / dp[1]
                for op2 in dp[-j - 1]: # dp[-1] = [5] / dp[-2] 
                    #print(op1,op2,"op들")
                    all_case.add(op1 - op2)
                    all_case.add(op1 + op2)
                    all_case.add(op1 * op2)
                    if op2 != 0:
                        all_case.add(op1 // op2)
        print(all_case, "추가된것들")
        if number in all_case:
            answer = i
            break
            
        dp.append(all_case) 
    #print(dp)
    return answer