[프로그래머스] 코딩테스트 연습 - N으로 표현 (Python)

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

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

처음 문제를 보았을 때 DP보다는 BFS가 먼저 떠올라서 BFS로 한참을 시도하다가 처리해야 하는 경우가 너무 많아져서 DFS로 변경했네요.

 

풀이

1. DFS를 이용한 완전 탐색

DFS를 사용하면 하나의 단계에서 4가지 갈래가 나오게 됩니다.

그리고 완전 탐색을 진행하므로 일정한 크기의 트리구조를 순회하는 것과 같아져서 일정한 속도로 탐색할 수 있게 됩니다.

 

 

Code

from collections import deque
def dfs(base, target):
    queue = deque([[0, 0]])
    mins = -1
    while queue:
        curr, step = queue.pop()
        if curr == target and (mins > step or mins == -1):
            mins = step
        elif step > 8:
            continue
        else:
            for i in range(1, 9):
                if step+i > 8: break
                temp = int(str(base)*i)     # 연속된 숫자 만들기
                queue.append([curr + temp, step + i])   # +연산
                queue.append([curr - temp, step + i])   # -연산
                queue.append([curr * temp, step + i])   # *연산
                queue.append([int(curr / temp), step + i])  # /연산
    return mins

def solution(N, number):
    return dfs(N, number)

 

 

문제 설명

아래와 같이 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