[프로그래머스] N으로 표현(Python)- DP

프로그래머스 - N으로 표현

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

N과 number이 주어졌을 때,
N만을 사용해서 사칙연산을 해서 number을 만들 때, N이 최소개로 쓰이는 경우의 수를 찾는 문제.(NN, NNN, NNNN..인 경우도 포함)
ex) N = 2, number = 11이면 22 // 2 = 11이 2가 3개 쓰여서 11을 만들 수 있는 최소의 개수

💡IDEA

1번 사용해서 만들 수 있는 수들, 2번 사용해서 만들 수 있는 수들, 3번 사용해서 만들 수 있는 수들.........을 찾아나가다가, 그 수들 중에 number이 포함되면 멈추고 리턴하면 된다.

dp 원리는
3번 사용해서 만들 수 있는 수들 =
1번 사용해서 만들 수 있는 수들 [사칙연산] 2번 사용해서 만들 수 있는 수들 +
2번 사용해서 만들 수 있는 수들 [사칙연산] 1번 사용해서 만들 수 있는 수들

이런식으로 dp 배열을 꾸려 나가면 된다.

def solution(N, number):
    answer = -1
    if N == number: return 1
    dp = []
    # N을 i번 사용해서 만들 수 있는 수들
    for i in range(1, 9):
        arr = set()
        # check는 5, 55, 555 이런식으로 붙여서 만드는 수
        check = int(str(N) * i)
        arr.add(check)
        for j in range(0, i - 1):
            # i번 사용해서 만들 수 있는 수 = [j번 사용] +,-,*,// [N - j번 사용]
            for op1 in dp[j]:
                for op2 in dp[-j-1]:
                    arr.add(op1 - op2)
                    arr.add(op1 + op2)
                    arr.add(op1 * op2)
                    if op2 != 0: arr.add(op1 // op2)
        if number in arr:
            answer = i
            break
        dp.append(arr)

    return answer

print(solution(5, 12))
print(solution(2, 11))