프로그래머스: N으로 표현

문제

코딩테스트 연습 - N으로 표현

 

문제 풀이

 특정한 숫자 `N`으로 사칙연산을 사용하여 `number`를 표현할 수 있는지 찾는 문제이다. 이때 `N`을 사용한 횟수가 가장 작은 경우를 찾아야 한다. 문제를 풀기 위해서는 `DP`를 통해서도 풀 수 있지만, `DFS`를 통해 풀더라도 간신히 통과할 수 있다.

 

 `DFS`를 통해 사용한 `N`의 수를 카운트하고, 카운트된 수가 8보다 크다면 더 이상 가지를 뻗을 필요 없이 종료하면 된다. 또한 만족하는 경우를 찾은 경우, 현재 찾은 카운트보다 `N`을 더 많이 사용한다면 가지를 뻗지 않으면 보다 시간을 단축시킬 수 있다.

 

코드

from math import inf


answer = inf


def dfs(n, cnt, num, number):
    global answer

    if answer < inf and cnt > answer:
        return
        
    if cnt > 8:
        return

    if num == number:
        answer = min(answer, cnt)
        return

    next_num = 0
    for i in range(8):
        next_num = next_num * 10 + n
        dfs(n, cnt + 1 + i, num + next_num, number)
        dfs(n, cnt + 1 + i, num - next_num, number)
        dfs(n, cnt + 1 + i, num * next_num, number)
        dfs(n, cnt + 1 + i, num / next_num, number)


def solution(N, number):
    dfs(N, 0, 0, number)
    return -1 if answer == inf else answer