[프로그래머스] N으로 표현 / python

DP 배열에서 DP[N]을 N + 1개의 5로 만들 수 있는 모든 경우의 수라고 하자.

DP[N]을 만들기 위해서는 a + b = N - 1이 되는 a개, b개로 만들 때의 경우의 수들이 필요하다.

예를 들면, DP[4]를 만들기 위해서는 (0,3) (1,2) (2,1) (3,0)이 4가지 경우가 필요하다.
우선 중복을 없애기 위해 set을 하나 만들고,
DP[0]과 DP[3]를 이중 for문 돌면서 사칙연산을 한 결과를 set에 추가해준다.
DP[1]과 DP[2]를 이중 for문 돌면서 사칙연산을 한 결과를 set에 추가해준다.
DP[2]과 DP[1]를 이중 for문 돌면서 사칙연산을 한 결과를 set에 추가해준다.
DP[3]과 DP[0]를 이중 for문 돌면서 사칙연산을 한 결과를 set에 추가해준다.
만약 set에 표현하고자 하는 값이 존재한다면 N + 1을 리턴한다.
존재하지 않는다면 DP[4] = set을 해주고 DP[5]에서 위의 과정을 다시 반복한다.

위의 방법으로 N의 조건 만큼 1에서 9까지 반복한다.

def solution(N, number):
    answer = -1
    DP = []

    for i in range(1, 9):
        num_set = { int(str(N) * i) }

        for j in range(0, i - 1):
            for x in DP[j]:
                for y in DP[-j - 1]:
                    num_set.add(x + y)
                    num_set.add(x - y)
                    num_set.add(x * y)

                    if y != 0:
                        num_set.add(x // y)

        if number in num_set:
            return i

        DP.append(num_set)

    return answer