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

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

1) 코드

def solution(N, number):
    if N == number:
        return 1 
    
    dp = [set() for _ in range(9)]
    
    for i in range(1, 9):
        dp[i].add(int(str(N)*i))
        
    
    for i in range(1, 9):
        for j in range(i):
            for x in dp[j]:
                for y in dp[i-j]:
                    dp[i].add(x+y)
                    dp[i].add(x-y)
                    dp[i].add(x*y)
                    
                    if y != 0:
                        dp[i].add(x // y)
        
        if number in dp[i]: 
            return i
        
    return -1
                        

2) 해설

• 많은 응용력이 필요한 DP 문제이다
  -> 길이가 8인 set()을 선언해서, 해당 set에 가능한 케이스들을 모두 Memoization 하면서 문제를 해결해나간다
  -> 반드시 복습이 필요한 문제이다.