프로그래머스 N으로 표현

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

가능한 조합의 모든 경우의 수에 대해서 생각해봐야 하는데, 동적계획법을 통해 가능한 조합을 incremental approach로 접근할 수 있었다.

사용한 N의 개수에 대한 dp를 통해 이전 N의 개수에 대한 수의 조합을 통해 현재의 조합을 생성할 수 있다.

처음엔, 바로 이전에 사용한 N-1을 통해 N개를 사용한 수 집합을 만들었는데 실패가 났었고,
해당 테스트 케이스에 대해서 커버하지 못했다.

• 12 = 5 + 5 + (5 / 5) + (5 / 5)

이전의 위의 경우에 n이 2가지인 경우와 4가지인 경우의 합으로 표현할 수 있는데, 5가지인 경우에서는 만들지 못하였다.

i의 값은 N의 개수에 따른 증가값이고,
i의 값을 만드는 조합들이 필요했기 때문에 반복문을 하나 더 생성하였는데,
예를 들어 6의 경우에 다음과 같은 조합이다
1 + 5
2 + 4
3 + 3
4 + 2
5 + 1
이러한 조합이 나오는데 절반까지만 하면 나머지는 같은 결과이기 때문에 i의 절반만 반복문을 돌았다.
조합을 만들고 가능한 연산을 dp에 add하고 해당 값이 존재하면 현재 i값을 반환, 아니면 -1을 반환하였다.

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