N으로 표현

• 0에서부터 시작해서 k를 증가시켜가면서 N을 k번 사용해서 만들 수 있는 모든 수를 만들어보고 그 중에 number가 있는지 확인해본다.
• N을 k번 사용해서 만들 수 있는 모든 수를 찾는 것은 DP를 이용한다
• dp[k] 를 N을 k번 사용해서 만들 수 있는 수의 집합이라고 하면
  • $ dp[i] = \bigcup_{j=1}^i \bigcup_{a\in dp[j]} \bigcup_{b\in dp[i-j]}\left\{a+b, a-b, a \times b, a \div b \right\} $ 으로 점화식을 세워진다.
• 시간복잡도를 구해 보려했으나 만만치 않다..
  • 각 dp[i]의 크기 |dp[i]| = O(sigma( 4 * |dp[j]| * |dp[i - j]| ) + 1) 으로 카탈랑 수 (Catalan number)에 4^i를 곱한 형태로 나온다. 즉, O(4^(2i) / i^(3/2)). 이 크기는 dp[i]를 만들기 위한 연산 횟수와 동일하니까, 전체 연산 수는 O(|dp[1]| + |dp[2]| + … + |dp[m]|) 인데… 이거는 너무 범위가 크다; 다른 방법을 생각하자
  • 각 dp[i]의 크기의 바운드를 N을 i번 써서 만들수 있는 최소값과 최대값으로 생각하자..
    • N을 i번 써서 만들수 있는 최대값은 그냥 N을 i번 붙여쓴 NNN….N이다. 최대값=N*(10^i-1)/9 이고 최소값도 -만 붙이면 되니까 |dp[i]| = O(N*10^i).
    • dp[i]를 계산할 때는 O(sigma( 4 * |dp[j]| * |dp[i - j]| ) + 1) 의 연산이 필요한건 동일하다. O(i*4*N^2*10^i)
    • 이 값을 i≤m 까지 모두 더한 합은 대충 O(N^2*m*10^m)
    • 16^m 이 포함되어있던 위의 식보다는 좀더 타이트해지긴 했지만.. 만족스럽지는 못하다. 그러나 이게 나의 한계인듯 ㅜ
• 이렇게 bottom-up으로 dp를 만들지 않고서 top-down으로 number에서부터 시작해서 만들어가려 하는 것은 “나누기 연산에서 나머지는 무시합니다.” 라는 조건때문에, 좀 힘들다. f(x) = min(f(x+N), f(x-N), f(x/N), f(x*N), f(x*N+1), f(x*N+2), …)+1 이런식이 되기 때문이다.

"""Solution code for "Programmers 42895. N으로 표현".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42895
- Solution link: http://www.teferi.net/ps/problems/programmers/42895
"""

MAX = 8


def solution(N, number):
    dp = [set() for _ in range(MAX + 1)]
    dp[0] = {0}
    for i in range(1, MAX + 1):
        dp[i] = {int(str(N) * i)}
        for j in range(1, i):
            for n1 in dp[j]:
                for n2 in dp[i - j]:
                    dp[i] |= {n1 + n2, n1 - n2, n1 * n2}
                    if n2 != 0:
                        dp[i].add(n1 // n2)
        if number in dp[i]:
            return i        
    return -1