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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42895

N으로 표현은 사칙 연산만으로 숫자 N을 이용해 문제에서 제시하는 number와 같은 숫자로 만들어야 하는 문제입니다. 중요한 점은 Dynamic Programming 기법을 적용하면 매우 빠른 시간에 풀이를 할 수 있다는 점입니다.

Dynamic Programming은 이전 수행 결과를 이용해 반복되는 연산을 모두 제거하는 알고리즘 기법입니다. fibonacci 수열과 같은 문제를 예로 들 수 있으나 생략하도록 하겠습니다.(fibonacci 설명: https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95?from=%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95)

1. 이 문제에 Dynamic Programming을 적용하는 방법은 N을 i개 사용했을 때 만들어진 연산 결과를 dp 리스트에 담는 것입니다. 이렇게 되면 dp 리스트에는 i개의 하위 결과 리스트들이 만들어지고 N 1개로 만든 결과 operation N 2개로 만든 결과 = N 3개로 만든 결과와 같이 이전 결과를 재사용할 수 있습니다.

2. 이제 또 다른 문제는 연산자 -,/의 경우 앞뒤 피연산자의 순서가 결과값을 결정하므로 피연산자의 순서를 바꾼 경우 또한 고려해야 합니다.
   여러 구현 방법이 있겠지만 필자는 모든 경우를 순회하도록 구현했습니다. 이렇게 하지 않고 first - second, second - first를 두번 적용해주면 훨씬 간단한 코드를 만들 수도 있습니다.

3. N과 N을 직접 이어붙이는 경우를 포함해야 합니다. 이런 경우는 N = 5일 때, 55와 555같은 경우를 포함합니다. 필자는 생각보다 불편하게? 구현했는데 사실 하위 리스트를 선언할 때 i개를 이어붙인 결과를 포함시키게 하면 되더라구요? 이 방법을 사용할 것을 권합니다...

answer_set = {int(str(N)*i)}

실제 제출 코드입니다. 최종적으로 dp 리스트의 하위 리스트들은 set으로 구성해야 중복도 제거되고 시간 또한 절약됩니다.

def solution(N, number):
    dp = [{}, {N}]
    if N == number:
        return 1
    for i in range(2, 9):
        answer_set = set()
        for j in range(1, i):
            for first in dp[j]:
                for second in dp[i-j]:
                    if first == int(str(N)*j) and second == int(str(N)*(i-j)):
                        answer_set.add(int(str(first) + str(second)))
                    answer_set.add(first + second)
                    answer_set.add(first - second)
                    answer_set.add(first * second)
                    if second != 0:
                        answer_set.add(first // second)
        if number in answer_set:
            return i
        dp.append(answer_set)
    return -1