N으로 표현 - Dynamic Programming

 

생각하기 상당히 막막했다. 그래서 솔루션을 보았는데, 이를 이해하는데에도 시간이 좀 걸렸다.

 

풀이방법

1. 5를 사용하는 갯수에따라 집합을 만든다.
2. 5을 3번 사용한다면, 1번 + 2번, 2번 + 1번, 의 경우의 수가 나올 수 있고, 겹치는 답을 제외하기 위해서 집합을 사용한다.
3. for문을 통해서 이를 모두 구해준다.

소스코드

def solution(N, number):
    answer = 0
    dp = [set() for _ in range(11)]
    for i in range(1,9):
        dp[i-1].add(int(str(N)*i))
        for j in range(i):
            for k in dp[j]:
                for l in dp[i-j-2]:
                    dp[i-1].add(k + l)
                    dp[i-1].add(k - l)
                    dp[i-1].add(k * l)
                    if l != 0:
                        dp[i-1].add(k // l)
            if number in dp[i-1]:
                return i 
    return -1