Step 6: 동적계획법(Dynamic Programming) 대표 문제 풀이: N으로 표현

강의

"동적계획법"은 최적화 문제를 재귀적인 방식으로 작은 부분 문제로 나누어 해를 조합하여 전체 문제의 해답에 이르는 알고리즘 입니다.

탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있습니다.

 

응용

• Knapsack Problem

 

 

Step 6-3: 풀어서 내 것으로 만들자! N으로 표현

⭐ 힌트 풀이 : 이전에 기록한 값을 다시 계산하도록 구현하는 문제!

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