문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42895

---

문제 파악

N, number 가 주어진다.
N이라는 1이상 9이하 정수를 이용해서
1이상 32,000 이하 정수 number를 만들어야 한다.

N을 쓸 수 있는 방법은 두가지가 있다.

1. N을 문자열처럼 이어붙이기

   • 예: N=5라면 5, 55, 555 처럼 만들 수 있다.

2. N을 이용한 사칙연산

   • 예: N=5
     • 5+5=10
     • 5-5=0
     • 5*5=25
     • 5/5=1 (문제에서는 정수 나눗셈으로 처리)

그리고 문제에 N을 최대 8번까지만 사용할 수 있다고 조건을 붙였다.

N을 사용해서 number를 만들 수 있다면 최소 사용 횟수를 return,
만들 수 없다면 -1을 return 하는 문제이다.

---

어떻게 풀 수 있을까?

N을 1개 사용해 만들 수 있는 가짓수 = 1개

N을 2개 사용해 만들 수 있는 가짓수 = 위에서 본 NN 붙이기, 그리고 사칙연산 4가지해서 총 5가지이다.

그렇다면 N을 3개 사용해 만들 수 있는 가짓수 어떻게 구할까?

이는 우선
NNN 붙인 가짓수 1개,

그리고 N을 1개 사용해 만들 수 있는 가짓수와 N을 2개 사용해 만들 수 있는 가짓수를 사칙연산 해주는 가짓수가 되겠다.

그리고 사칙연산에 곱하기 나누기도 있으니까 연산 순서가 결과에도 영향을 미치니, 순서까지 고려해주면

N을 3개 사용해 만들 수 있는 가짓수는

• NNN
• N을 1개 사용해 만들 수 있는 가짓수 더하기/빼기/곱하기/나누기 N을 2개 사용해 만들 수 있는 가짓수
• N을 2개 사용해 만들 수 있는 가짓수 더하기/빼기/곱하기/나누기 N을 1개 사용해 만들 수 있는 가짓수

이렇게가 되시겠다.

그럼 K가 4라면?

• NNNN
• N을 1개 사용해 만들 수 있는 가짓수 더하기 / 빼기 / 곱하기 / 나누기 N을 3개 사용해 만들 수 있는 가짓수
• N을 2개 사용해 만들 수 있는 가짓수 더하기 / 빼기 / 곱하기 / 나누기 N을 2개 사용해 만들 수 있는 가짓수
• N을 3개 사용해 만들 수 있는 가짓수 더하기 / 빼기 / 곱하기 / 나누기 N을 1개 사용해 만들 수 있는 가짓수

이다..

K가 i라면?

• N을 i번 이어붙인 수 (NN...N, i개)

• N을 1개 사용해 만들 수 있는 가짓수 더하기 / 빼기 / 곱하기 / 나누기 N을 (i-1)개 사용해 만들 수 있는 가짓수

• N을 2개 사용해 만들 수 있는 가짓수 더하기 / 빼기 / 곱하기 / 나누기 N을 (i-2)개 사용해 만들 수 있는 가짓수
  …

• N을 (i-1)개 사용해 만들 수 있는 가짓수 더하기 / 빼기 / 곱하기 / 나누기 N을 1개 사용해 만들 수 있는 가짓수
  이다.

즉, N을 i번 이어붙인 수와, i를 두 덩어리로 나눌 수 있는 모든 방법에 대해
이미 구해 둔 dp들을 서로 사칙연산으로 합쳐보는 방식이다.

for i in range(1, k):
    for a in dp[i]:
        for b in dp[k-i]:

는 이 코드가 된다.

해답 코드

def solution(N, number):
    # dp[k] = k번 N을 사용해 만들 수 있는 값들
    dp = [set() for _ in range(9)] # 문제조건 : 만약 8보다 크다면 -1 return
# dp = [
#     set(),  # dp[0] 은 더미
#     set(),  # dp[1] N을 1개 사용해 만들 수 있는 값들
#     set(),  # dp[2] N을 2개 사용해 만들 수 있는 값들
#     set(),  # dp[3] N을 3개 사용해 만들 수 있는 값들
#     ...
#     set()   # dp[8] N을 9개 사용해 만들 수 있는 값들
# ] 
    for k in range(1,9):
        # 1) N을 붙이는 수 NN,NNN..
        concat = int(str(N) * k)
        dp[k].add(concat) # 집합이라 add 메서드 사용
        
        # 2) 사칙연산
        for i in range(1, k):
            for a in dp[i]:
                for b in dp[k-i]:
                    dp[k].add(a + b)
                    dp[k].add(a - b)
                    dp[k].add(a * b)
                    if b!= 0:
                        dp[k].add(a//b)
        
        # 타겟이 dp[k]안에 있다면 바로 k return                        
        if number in dp[k]:
            return k
        
    return -1 # k가 return 되지 않았다면? number가 안만들어진다는 뜻

dp 방향성을 잡더라도, 점화식을 떠올리고, 코드로 옮기기가 어려운 문제였다.