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

문제

• 숫자 N와 사칙연산만으로 number 표현할 수 있다. N을 최소 횟수 리턴하기
  • 1 <= N <= 9
  • 1 <= number <= 32,000
• 수식에서 괄호와 사칙연산만 가능하고 나누기 연산에서 나머지는 무시한다.
• 최솟값이 8보다 크면 -1을 리턴한다.

 

풀이

• dp[i] : i를 만들기 위한 N의 최솟값
• N을 하나씩 늘리면서 각 N의 개수별로 만들 수 있는 숫자를 확인한다.
  • N을 k개 사용한다고 하면 아래의 경우의 수를 확인하면 된다.
    • k-1 개로 만들 수 있는 숫자 (연산 +-*/) 1개로 만들 수 있는 숫자
    • k-2 개로 만들 수 있는 숫자 (연산 +-*/) 2개로 만들 수 있는 숫자
    • ...
    • 1개로 만들 수 있는 숫자 (연산 +-*/) k-1 개로 만들 수 있는 숫자

 

from collections import defaultdict

def solution(N, number):
    MAX = 32000
    
    # dp[i] : N을 i개 사용해서 만들 수 있는 숫자들
    dp = defaultdict(set)
    for i in range(1, 9) :
        dp[i].add(int(str(N)*i))
        if number in dp[i] :
            return i
    
    # DP; N 1개씩 늘리기
    for i in range(2, 9):
        for j in range(1, i) :
            for num in dp[i-j]:
                for num2 in dp[j] :
                    dp[i].add(num+num2)    # 덧셈
                    dp[i].add(num-num2)    # 뺄셈
                    dp[i].add(num*num2)    # 곱셈
                    if num2 != 0:
                        dp[i].add(num//num2)   # 나눗셈
        if number in dp[i]:
            return i
    return -1

 

References

• 프로그래머스 고득점Kit DP