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

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

프로그래머스

⚡️ 문제 설명

⚡️ 해결 방법

5를 1번 사용해서 만들 수 있는 수 set

{5}

 

5를 2번 사용해서 만들 수 있는 수 set

{0, 1, 10, 55, 25}

 

5를 3번 사용해서 만들 수 있는 수 set

= 5를 2번 사용해서 만들 수 있는 수  set 과 5를 1번 사용해서 만들 수 있는 수 set 의 사칙연산 한 set

{0, 2, 4, 5, 6, 555, -20, -4, -50, 15, 11, 50, 275, 20, -5, 60, 125, 30}

 

⚡️ 코드

 

def solution(N, number):
    answer = -1
    
    dp = []
    
    for i in range(1,9):
        numbers = set()
        numbers.add(int( str(N) * i))
        
        for j in range(i-1):
        # dp[j] 과 dp[-j-1] 의 사칙연산 set 구하기
            for a in dp[j]:
                for b in dp[-j-1]:
                    numbers.add(a+b)
                    numbers.add(a-b)
                    numbers.add(a*b)
                    if b != 0:
                        numbers.add(a//b)
            
        if number in numbers:
            answer = i
            break
        dp.append(numbers)
        
    return answer