1. 문제 설명

N으로 표현

2. 문제 분석

지금 단계에서 나온 solution이 이후 단계에서 활용하는 문제이다. 사칙연산의 경우 합과 곱은 순서가 상관없지만 뺄셈과 나눗셈은 순서에 따라 값이 달라지는 것에 주의. 중복 숫자를 제거하기 위해 set을 활용했다.

1. N을 i번 사용해 만들 수 있는 수는 (사칙연산 사용 X)와 (사칙연산 사용 O)이다. 전자는 단순히 N개를 i번 나열하면 된다.
2. 사칙연산을 사용한 경우 N을 (1, 2, ..., i-1)번 사용해 만들어낼 수 있는 수 목록을 활용한다.

• N을 4번 사용해 만들 수 있는 수들을 구하기 위해서는,

N을 4번 사용해야 하는 경우 = 
(1). (N을 1번 사용해 만든 수들) +-*/ (N을 3번 사용해 만든 수들) 
(2). (N을 2번 사용해 만든 수들) +-*/ (N을 2번 사용해 만든 수들)

즉 위처럼 이미 앞에서 i번보다 작은 경우의 수를 통해 "구해 놓았던" dp를 써서 지금 i번 쓸 수 있는 수들을 구해야 한다.

3. 나의 풀이

def calculator(j, k):
    tmp = []
    tmp.append(j+k)
    tmp.append(j*k)
    tmp.append(j-k)
    tmp.append(k-j)
    if k != 0: tmp.append(j//k)
    if j != 0: tmp.append(k//j)
    return tmp

def solution(N, number):
    dp = [[0]]
    # dp[n] -> n개의 N을 사용했을 때 만들어지는 수를 담은 배열
    for i in range(1, 9):
        tmp = set()
        base = int(str(N)*i)
        tmp.add(base)
        # 사칙연산 사용 X

        for idx in range(1, i):
            for j in dp[idx]:
                for k in dp[i-idx]:
                    # N을 2개 쓴 경우 -> 1개 쓴 경우를 두 번 활용
                    # N을 3개 쓴 경우 -> 1개 쓴 경우 + 2개 쓴 경우 활용
                    # N을 4개 쓴 경우 -> 1개 쓴 경우 + 3개 쓴 경우 활용 / 2개 쓴 경우 + 2개 쓴 경우
                    #... N을 i개 쓴 경우 -> idx개 쓴 경우 + (i-idx)개 쓴 경우
                    for item in calculator(j, k):
                        tmp.add(item)
                        # 집합 tmp는 j와 k를 활용한 모든 사칙연산 결과를 포함 -> 중복값 제거
        if number in tmp:
            return i
        # N을 i개 쓴 tmp 차례에서 number 발견
        tmp = list(tmp)
        dp.append(tmp)

    return -1