Programmers :: 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 합니다.

🤔 생각

• DP 카테고리라서 DP 쪽으로 생각을 해봤지만...

• 점화식이 잘 떠오르지 않았다. 아무래도 n이 한 수에 연속해서 붙는 경우 때문에 복잡했다.

• DP 문제인걸 몰랐다면 백트래킹으로 접근했을 것 같다.

• 백트래킹으로 해보자!

설계

N (+ - / )...
NN ( + - / )....
NNN ...
NNNN...

이런 식으로 N을 늘려가며 재귀호출하자

📌 내 풀이

ans = 9

def solution(N, number):
    def dfs(cnt, res):
        if cnt > 8:
            return
        if res == number:
            global ans
            ans = min(cnt, ans)
            return

        tmp = 0
        for i in range(8):
            tmp = tmp*10 + N
            dfs(cnt+i+1, res+tmp)
            dfs(cnt+i+1, res-tmp)
            dfs(cnt+i+1, res*tmp)
            dfs(cnt+i+1, res//tmp)

    dfs(0,0)
    return ans if ans != 9 else -1