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

난이도가 높지는 않은 문제.

N을 1개씩 늘려가면서 완전탐색하되, number가 있는지 확인한다.

예컨대... 5가 네개인 경우를 완전탐색하려면, (5, 5, 5, 5)

(5) + (5, 5, 5)

(5, 5) + (5, 5)

(5, 5, 5) + (5)

위의 모든 케이스를 다 따져 주면 된다.

여기서 +는 더하라는 의미가 아니라,

왼쪽에서 발생되는 모든 케이스와 오른쪽에서 발생되는 모든 케이스를 조합하는 모든 케이스를 생성하라는 의미이다.

def solution(N, number):
    if number == N:
        return 1
    dp = [[] for _ in range(9)]
    dp[1] = [N]
    for i in range(2, 9):
        dp[i].append(int(str(N)*i))
        for j in range(1, i):
            for x in dp[j]:
                for y in dp[i-j]:
                    dp[i].append(x+y)
                    dp[i].append(x-y)
                    dp[i].append(x*y)
                    if y != 0:
                        dp[i].append(x//y)
        dp[i] = list(set(dp[i]))
        if number in dp[i]:
            return i
    return -1