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

문제링크

 

문제 조건이 속삭이고 있다. 마음껏 Brute-force 탐색하라고. 즉, 이 문제는 DP 문제이다.

 

정답 코드

def solution(N, number):
    
    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(1, i) :
            for a in dp[j] :
                for b in dp[i-j] :
                    dp[i].add(a+b)
                    dp[i].add(a-b)
                    dp[i].add(a*b)
                    if b != 0 :
                        dp[i].add(a//b)
                        
        if number in dp[i] :
            return i

    return -1