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

• 링크: https://programmers.co.kr/learn/courses/30/lessons/42895

def solution(N, number):
    if N == number:
        return 1

    candidate = {1:[N, -N]}
    key = 2

    while True:
        new_candidate = set()
        new_candidate.add(int(str(N) * key))
        new_candidate.add(-int(str(N) * key))

        for i in range(1, key):
            lst_x = candidate[i]
            lst_y = candidate[key - i]

            for x in lst_x:
                for y in lst_y:
                    new_candidate.add(x + y)
                    if y != 0:
                        new_candidate.add(x // y)
                    new_candidate.add(x * y)
                    new_candidate.add(x - y)

        candidate[key] = list(new_candidate)

        if number in candidate[key]:
            return key

        key += 1

        if key > 8:
            return -1

• 다이나믹프로그래밍 중 메모이제이션을 사용해서 풀었다. N을 k번 사용해서 나올 수 있는 모든 값을 N(k)라고 할 때, N(k)는 <N(1), N(k-1)>, <N(2), N(k-2)>... 등의 조합으로 구할 수 있다. 따라서 N(k)는 더 하위 문제의 값들을 조합해서 만들어지는 분할정복이 가능한 문제라는 뜻이다.

• 이 코드에서 사용한 풀이는 N을 1번 써서 나올 수 있는 값, 2번 써서 나올 수 있는 값.. 을 딕셔너리에 저장하고 N을 3번 써서 나올 수 있는 값들을 구해야할 때엔 1번써서 나올 수 있는 값 리스트와 2번 써서 나올 수 있는 값 리스트를 불러와 조합하는 방식이다.

• N == number인 경우를 고려하지 못하여 생각보다 푸는 시간이 길어졌다.

• 이 코드에선 조합이 뒤집어지는 경우를 빼지 않았기 때문에 예를 들어 key가 3일 경우 (1, 2), (2, 1) 같은 식으로 두번씩 값을 구하게 되기 때문에 시간적으론 완전히 효율적이지 않다. key가 8일 경우까지만 고려하면 되기에 고치지 않았으나 이 부분을 고치면 더 완벽한 답이 될 것 같다.