프로그래머스 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 함수를 작성하세요.

제한사항

N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N number return
5 12 4
2 11 3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

과정

from collections import deque;

def solution(N, number):
    if number==N: return 1
    
    queue=deque()
    
    a=[int(N*10+N),int(N+N),int(N-N),int(N//N),int(N*N)]
    
    if number in a: 
        return 2
    queue.append(a)

    deep=2
    while queue:
        tmp=queue.popleft()
        deep+=1
        if deep > 8: break
            
        list=[]
        for i in range(len(tmp)):
            if tmp[i]*10+N <=32000: list.append(tmp[i]*10+N)
            if tmp[i]+N <= 32000:list.append(tmp[i]+N)
            if tmp[i]-N <= 32000: list.append(tmp[i]-N)
            if tmp[i]//N <= 32000:list.append(tmp[i]//N)
            if tmp[i]*N <= 32000: list.append(tmp[i]*N)
            if number in list: return deep
                
        queue.append(list)
        
    return -1

완전 탐색에 dp를 섞은식으로 진행해보았다. 하나씩 탐색해가면서 더하고 빼고했지만
8,53->5인경우에 실패하였다.
8*8-88/8로 5개가 되어야하지만 88을 도중에 만들어지지가않아서 그럴경우 진행이되지않았다.

코드

def solution(N, number):
    dp = [[]]
    for i in range(1, 9):
        temp = []
        for j in range(1, i):
            for k in dp[j]:
                for l in dp[i - j]:
                    temp.append(k + l)
                    if k - l >= 0:
                        temp.append(k - l)
                    temp.append(k * l)
                    if l != 0 and k != 0:
                        temp.append(k // l)
        temp.append(int(str(N) * i))
        if number in temp:
            return i
        dp.append(list(set(temp)))

    return -1

이 코드는 전 단계 즉 현재 만들고있는 n의 개수가 5일때 1,2,3,4의 데이터를 모두 가지고 있는 채로 쌓으면서 조합하며 만드는 코드이다. 이럴경우 위의 중간에서 88 이 해결될 수 있다.