[ Lv 3 ] N으로 표현

• 너무 어려워서 다른 사람들이 풀이한 것들을 참고함.. 동적 계획법이 약함.

풀이 과정

1. 각 단계에서 나올수 있는 수를 따로 table에 저장해 둠.
2. 현재 단계로 도달할 수 있는 모든 케이스에 대하여 set으로 저장한 후 table에 저장
   • 현재 단계가 4단계라면, 1단계 + 3단계, 2단계 + 2단계, 3단계 + 1단계로 4단계로 도달 가능하다.
   • 각각의 케이스에 대해 덧셈, 뺄셈, 곱셈, 나눗셈 검사
3. 현재 단계에서 number이 있는지 검사하고 있다면 바로 return

---

소스 코드

from collections import deque

def solution(N, number):
    answer = -1
    table = []
    for i in range(1, 9):
        middle_set = set()
        middle_set.add(int(str(N) * i)) # 쭉 붙인거는 따로 추가
        for j in range(0, i-1):
            for k in table[j]:
                for l in table[-j-1]:
                    middle_set.add(k + l)
                    middle_set.add(k - l)
                    middle_set.add(k * l)
                    if l != 0:
                        middle_set.add(k // l)
        if number in middle_set:
            return i
        table.append(middle_set)


    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges