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

---

1. 전체 코드

def solution(N, number):
    answer = -1
    if N == number:
        return 1
    d = [set() for i in range(9)]
    for i in range(1, 9):
        d[i].add(int(str(N) * i))  # [5, 55, 555, 5555...]
    for i in range(2, 9):
        for j in range(1, i):
            # 예) 5자리 숫자를 만들기 위해서는
            # 1+4, 2+3, 3+2, 4+1 네 개의 경우가 존재한다.
            # [j] 와 [i-j] 의 합은 항상 5가 나온다.
            for op1 in d[j]:
                for op2 in d[i-j]:
                    d[i].add(op1 + op2)
                    d[i].add(op1 - op2)
                    d[i].add(op1 * op2)
                    if op2 != 0:
                        d[i].add(op1 // op2)
        if number in d[i]:
            answer = i
            break
    return answer


solution(5, 12)

---

2. 후기

그동안 DP 문제를 풀 때, number 에 해당하는 dp 테이블을 만들어 1부터 값을 채워가면서 기존의 값을 재활용하면서 d[number]를 구했다. 하지만 이 문제는 그렇게 풀 수 없다.

N의 사용횟수(1~8)에 맞는 모든 경우를 저장하는 dp 테이블을 떠올리는게 쉽지 않은 문제이다. 본인은 생각하지 못했다. 이 문제가 dp인 이유는 [j]와 [i-j]로 기존의 값을 활용하는 부분에서 확인 가능하다.