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

문제 링크

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

프로그래머스

 

동적계획법(Dynamic Programming) 이용 문제

 

1. 점화식 의미 정의

dp[i]: N을 정확히 i번 사용하여 만들 수 있는 모든 수들의 집합

 

2. dp 초기화

N을 한 번 사용하면 표현할 수 있는 수는 N뿐 

dp[1] = {N} 

 

3. 반복구성 i = 2 ~ 8

dp[i]에 숫자를 이어붙인 값 int(str(N) * i)을 추가

1~i까지 j 변수를 통해 돌면서 dp[j]와 dp[i-j]를 이용해 + , -, *, // 사칙연산

 

i 반복문마다 dp[i] 배열에 number을 가지고 있는지 확인

만약 있으면 바로 반환

 

i를 끝까지 돌았는데도 없으면

-1 반환

 

코드

def solution(N, number):
    if N == number:
        return 1
    
    dp = [set() for _ in range(9)]
    dp[1].add(N)
    
    for i in range(2, 9):
        dp[i].add(int(str(N) * i))
        
        for j in range(1, 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