DP - N으로 표현(Lv.3)

• dp[i]는 N을 i번 써서 만들 수 있는 숫자들의 집합
• dp[i]를 만들기 위해 i를 j + (i - j)로 쪼개기
• dp[j]와 dp[i - j]에 있는 수들을 서로 사칙연산해서 dp[i]에 추가
  -> 이렇게 하면 N을 i번 써서 만들 수 있는 모든 조합 구해짐
• 목표 숫자가 dp[i]에 있으면 그 i가 최소 사용 횟수!

- dp[i] = N을 i번 써서 만들 수 있는 수 = N을 j번, (i-j)번 써서 만든 수끼리 연산해서 만든 수들의 집합

def solution(N, number):
    answer = 0
    # N을 한 번 썼을 때 바로 number가 되는 경우
    if N == number:
        return 1
    
    # dp[8]까지 사용
    dp = [set() for _ in range(9)] # dp[i]: N을 i번 써서 만들 수 있는 숫자들의 집합
    
    # i: 1~8
    for i in range(1, 9):
        dp[i].add(int(str(N) * i))
        
        for j in range(1, i): # j는 1 ~ i-1까지
            for op1 in dp[j]: # j번 쓴 숫자 집합에서 하나 꺼내기
                for op2 in dp[i - j]: # (i - j)번 쓴 숫자 집합에서 하나 꺼내기 -> j + (i - j) = 총 i번이 되도록
                    dp[i].add(op1 + op2) # 덧셈
                    dp[i].add(op1 - op2) # 뺄셈
                    dp[i].add(op1 * op2) # 곱셈
                    
                    if op2 != 0: # 나누는 수가 0이 아니면
                        dp[i].add(op1 // op2) # 나눗셈
        # dp[i]에서 목표 숫자를 만들 수 있다면 N의 사용 횟수인 i 리턴
        if number in dp[i]:
            return i
    
    
    # N을 8번 써도 못만들었다면 -1 리턴
    return -1