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

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42895

문제 설명
아래와 같이 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번만 사용하여 표현할 수 있습니다.

풀이

처음에는 deque와 DP를 사용하여서 풀려고하였다.
N이 5라고 하면 [5, 55, 555,... 55555]를 넣고 여기서 사칙연산을 하나씩 하면서 queue에 넣고 앞에 수를 하나빼서 또 사칙연산을 하고 넣고를 하려고 하였다.

from collections import deque


def solution(N, number):
    nums = [N, N*11, N*111, N*1111, N*11111]
    DP = [0] * (100001)
    for i in range(len(nums)):
        if nums[i] == number:
            return i+1
        DP[nums[i]] = i+1
    queue = deque(nums)
    while queue:
        now = queue.popleft()
        for i in range(len(nums)):
            order = DP[now]+i+1
            l = [now+nums[i], now-nums[i], now//nums[i], now*nums[i]]
            for j in l:
                if 0 <= j <= 100000:
                    if DP[j] == 0 or DP[j] > order:
                        DP[j] = order
                        queue.append(j)
    if DP[number] > 8 or DP[number] == 0:
        return -1
    else:
        return DP[number]

그러나 이렇게하면 여러 문제가 있었다.

1. 오래걸린다.
2. 100,000보다 큰 수가 연산 중에 나올 수도 있는데 이는 포함시킬 수 없다는 큰 맹점이 있다.
3. ⭐️ 괄호를 이용한 수식은 표현할 수 없다는 점이다.
   가령 (5+55)*(55+5) = 3600으로 6을 반환해야 하지만, 8이 나온다.

따라서 DP 설계를 N이 들어간 수로 하였다.
N을 1개로 표현할 수 있으면 DP[1]에 들어가고, 2개로 표현할 수 있으면 DP[2]에 들어가게 하였다.
중복될 수 있으므로 set()으로 초기화한다.

처음에 N = 5 라고 하면 [5, 55, 555, 5555 ,.. 555555]를 넣어주고 number와 일치하는 것이 있으면 바로 반환하였다.

for DP의 길이만큼 i는 2에서 8까지 돌 것이다.:

	for j는 1부터 i-1로 이는 괄호를 나누는 기준이 된다:

		(j개의 N으로 만들 수 있는 수) + (i-j개의 N으로 만들 수 있는 수)

		(j개의 N으로 만들 수 있는 수) - (i-j개의 N으로 만들 수 있는 수)

		(j개의 N으로 만들 수 있는 수) * (i-j개의 N으로 만들 수 있는 수)

		(j개의 N으로 만들 수 있는 수) // (i-j개의 N으로 만들 수 있는 수) → 0이 아닐 때만

	만들어진 수 중에 number가 있으면 i를 반환

8까지 돌았는데 없으면 -1 반환

최종코드

from collections import deque


def solution(N, number):    
    DP = [set() for _ in range(9)]
    pre = [N, N*11, N*111, N*1111, N*11111, N*111111, N*1111111]
    for i in range(len(pre)):
        if pre[i] == number:
            return i+1
        DP[i+1].add(pre[i])
    for i in range(2, 9):
        for j in range(1, i):
            for k in DP[i-j]:
                for h in DP[j]:
                    DP[i].add(k+h)
                    DP[i].add(k-h)
                    DP[i].add(k*h)
                    if h != 0:
                        DP[i].add(k//h)
        if number in DP[i]:
            return i
    return -1