27440 : 1로 만들기 3 Python

풀이 방법을 떠올리다가 처음에는 배열을 사용한 DP로 시도했는데, N이 10^18까지 가능해 배열로는 풀 수가 없는 문제였다. N이 워낙 크다보니 BFS로도 풀지 못할 것이라 생각해 시도조차 하지 않았었고 도저히 모르겠어서 알고리즘을 확인했는데 BFS가 있어서 놀랐다.

 

결국 BFS가 돌아갈 수 있었던 이유는 메모리가 1024byte로 모든 수를 메모이제이션 하기에는 부족하지만, BFS 큐 사이즈를 감당하기에는 충분했기 때문인 것 같다. BFS 특성상 모든 수를 다 돌아보지 않고 가장 빨리 도달하는 경우만 살펴보기 때문이다. 관건은 "-1연산을 최소화할 수 있는가?"인 것 같다.

BFS 풀이

추가적으로 새로 알았던 점은 defaultdict를 사용할 때 그동안 관습적으로 int를 넣어줬었는데 여기에 커스텀 메서드를 넣을 수 있다는 점이다. 여기서 메서드를 일급 함수로 넣어주면 defaultdict가 추후 키로 값을 찾을 때 없다면 인자로 넣어줬던 메서드의 반환값을 기본값으로 갖는다. 그렇기 때문에 defaultdict(lamdba : sys.maxsize)와 같이 작성했을 때 키에 대한 값이 없다면 sys.maxsize를 반환한다.

import sys
from collections import defaultdict
from collections import deque

# print = sys.stdout.write
input = sys.stdin.readline
# 반드시 아래 두 라인 주석 처리 후 제출
# f = open("input.txt", "rt")
# input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출
INF = sys.maxsize

N = int(input().rstrip())

v = defaultdict(lambda: INF)

v[N] = 0

def find():
    q = deque([(N, 0)])

    while q:
        num, cnt = q.popleft()

        if num == 1:
            return cnt

        if num - 1 > 1 and v[num - 1] > cnt + 1:
            q.append((num - 1, cnt + 1))
            v[num - 1] = cnt + 1

        if num % 2 == 0 and v[num // 2] > cnt + 1:
            q.append((num // 2, cnt + 1))
            v[num // 2] = cnt + 1

        if num % 3 == 0 and v[num // 3] > cnt + 1:
            q.append((num // 3, cnt + 1))
            v[num // 3] = cnt + 1

    return -1

def main():
    print(find())

if __name__ == "__main__":
    main()

DP 풀이

DP로 풀 경우 크게 두 가지 정도의 풀이 방법이 있었고 두 경우 모두 -1연산을 최소화하는 방법으로 동작했다. 또한 배열 대신 맵을 사용했다.

기존 1로 만들기에서 많이 사용했던 방법은 3으로 나누어떨어질 때와 2로 나누어 떨어질 때 모두 확인하는 방법이였다.

def find(num):
    if num < 1:
        return 0

    if num % 3 == 0:
            dp[num] = min(dp[num], find(num // 3) + 1)
    if num % 2 == 0:
            dp[num] = min(dp[num], find(num // 2) + 1)
    dp[num] = min(dp[num], find(num - 1) + 1)

    return dp[num]

하지만 위와 같이 구현할 경우 최악의 경우 -1 연산을 N만큼 수행해야 하는데 이 문제에서는 N이 10^18까지 있기 때문에 재귀 스택이 터지게 된다.

def find(num):
    if num in dp.keys():
        return dp[num]

    if num % 6 == 0:
        ret = min(find(num // 2), find(num // 3)) + 1
    elif num % 3 == 0:
        ret = min(find(num // 3), find(num - 1)) + 1
    elif num % 2 == 0:
        ret = min(find(num // 2), find(num - 1)) + 1
    else:
        ret = find(num - 1) + 1

    dp[num] = ret
    return dp[num]

그러므로 위와 같이 구현할 수 있다. 위에서 이야기했듯이 3과 2의 공배수일 경우 두 경우를 모두 확인해봐야 어느쪽이 더 적은 연산을 사용하는지 알 수 있다. 그리고 2와 3 중 어느 수로도 나누어 떨어지지 않는 경우에만 - 1 연산을 수행하도록 했다.

혹은 아예 %을 통해 - 1 연산을 명시적으로 수행하지 않는 경우도 있었다. 어떤 수 N에 대하여 d로 나누었을 때 몫이 r이라면 N - r은 d의 배수가 된다. 이를 활용해 -1을 d회 해서 N의 배수로 만들고 여기에 재귀로 나누기 연산을 수행해 최소 횟수를 더했다.

def find(number):
    if number in dp.keys():
        return dp[number]

    # number % N = rem이라 했을 때 number에서 rem을 빼면
    # 해당 수는 N의 배수가 된다
    result = 1 + min(find(number // 3) + number % 3, find(number // 2) + number % 2)
    dp[number] = result

    return dp[number]