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

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

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

 

해결 방법 : DP

• n개의 숫자N으로 만들 수 있는 수들을 dp[n] 이라고 한다면, a + b = n을 만족하는 모든 자연수 a, b에 대해
  • dp[n] = dp[a]와 dp[b] 사이의 모든 연산 결과 

def solution(N, number):
    dp = [[] for _ in range(8)]

    for i in range(8): # N이 1개 ~ 8개
        numbers = set([int(str(N) * (i + 1))]) # N의 개수가 한 숫자에 다 쓰인 경우

        for j in range(0, ((i + 1) // 2)): # 합이 i인 두 경우들에 대해 반복
            for x in dp[j]: 
                for y in dp[i - 1 - j]: # 생성 가능한 수들 추가
                    numbers.update([x + y, x - y, y - x, x * y])
                    if x != 0: numbers.add(y // x)
                    if y != 0: numbers.add(x // y)

        if number in numbers:
            return i + 1

        dp[i].extend(numbers)

    return -1