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

N으로 표현

생각 흐름

1. 프로그래머스에서 들어갔으므로 dp를 사용해야 한다는 것을 이미 알고 있다.
2. dp를 이용하는 방법
   1. dp[i] => i를 5로 표현할 때 필요한 N의 최소 개수?
   2. 이 경우 dp[i] 를 구할 때 dp[1 ~ i-1]을 어떻게 이용할까
      -> 굉장히 어렵고 일관적이지 않은 방법
   3. N, NN, NNN... 과의 사칙연산의 모든 조합을 구하는 것인가?
3. 고민해 본 뒤 정답이 나오지 않아 풀이를 찾아보았다.

풀이

정답은 내가 했던 생각의 2-3에서 출발한다.
N을 i번 써서 number을 표현할 수 있는 수들은
N을 각각 (1번, i-1번), (2번, i-2번), ... (j번, i-j번) 써서 표현할 수 있는 수들을
교차해서 사칙연산한 결과 + N{i} 이다.

N=5라고 할 때,
1: 5
2: 55, 5+5, 5-5, 55, 5/5
3: 555, 55+5, 55-5, 555, 55/5, 5+5+5, 5+5-5, 5-5-5, 5*5-5, 5/5-5...

i=3 의 경우의 수는 i=1에 있는 것들과 i=2에 있는 것들을 교차해서 사칙연산한 집합이다.

내가 생각을 2-3에서 시작해서
dp 배열에 항상 '숫자 하나'만 들어가는 게 아닌 경우의 수, 집합 등 다양한 자료값이 들어갈 수 있다고 생각했더라면 풀 수 있는 문제였다.

이 문제로 dp를 좀 더 다양하게 풀 수 있게 되었다.

코드

def solution(N, number):
    dp = [set() for _ in range(9)]
    for i in range(1, 9):
        dp[i].add(int(str(N) * i))
        
        for j in range(1, i):
            for x in dp[i - j]:
                for y in dp[j]:
                    add_num(dp[i], x + y)
                    add_num(dp[i], x - y)
                    add_num(dp[i], x * y)
                    add_num(dp[i], x // y)
                    
        if number in dp[i]:
            return i
                    
    return -1
                    
                    
def add_num(d, x):
    if x != 0:
        d.add(x)

add_num(d, x) 함수는 어차피 dp[i]에 들어갈 값이 0이면 넣어줄 필요가 없으므로 이에 대한 예외처리를 하도록 따로 뺀 함수이다.