[Algorithm Problem] 1로 만들기2 (BAEKJOON: 12852번)

Make Number to One 2 (1로 만들기2)

이 문제는 반복적 동적 계획법을 이용해 간단하게 풀 수 있는 문제인 1로 만들기의 확장판입니다. 풀이는 같으나 여기에 경로를 업데이트하여 추적하는 방법을 추가합니다. 저는 메모리 효율은 고려하지 못 한 아래와 같은 러프한 풀이를 사용했습니다.

if __name__=="__main__":
    N = int(input())

    # dp 초기화
    dp = [float('inf') for _ in range(N+1)]
    dp_path = [[] for _ in range(N+1)]
    dp[1] = 0
    dp_path[1] = [1]

    for i in range(1, N+1):
        if i + 1 <= N and dp[i] + 1 < dp[i + 1]:
            dp[i + 1] = dp[i] + 1
            dp_path[i + 1] = dp_path[i] + [i + 1]

        if i * 2 <= N and dp[i] + 1 < dp[i * 2]:
            dp[i * 2] = dp[i] + 1
            dp_path[i * 2] = dp_path[i] + [i * 2]

        if i * 3 <= N and dp[i] + 1 < dp[i * 3]:
            dp[i * 3] = dp[i] + 1
            dp_path[i * 3] = dp_path[i] + [i * 3]

    print(len(dp_path[N]) - 1)
    dp_path[N].sort(key=lambda x:-x)
    print(*dp_path[N])

1은 연산 횟수가 0번 필요하고 그 경로는 [1] 자기 자신입니다. 그 이후는 칸을 한 칸씩 옆으로 이동하며 자기 칸에서 이동할 수 있는 모든 칸으로 +1 값을 해줍니다. 이때, 해당 칸이 이미 다른 숫자에서 이동할 수 있는 칸이며 연산 횟수가 더 적다면 이동하지 않습니다. 반대로 더 적은 연산횟수로 도달할 수 있는 수라면 해당 칸의 dp[n] 값을 수정하고, 이전까지의 경로로 업데이트하고, 마지막으로 자기 경로를 더합니다.

1로 만들기는 경로는 상관하지 않고, dp[N] 값만을 출력하면 정답을 맞출 수 있습니다.

if __name__=="__main__":
    N = int(input())

    # dp 초기화
    dp = [float('inf') for _ in range(N+1)]
    dp[1] = 0

    for i in range(1, N+1):
        if i + 1 <= N and dp[i] + 1 < dp[i + 1]:
            dp[i + 1] = dp[i] + 1

        if i * 2 <= N and dp[i] + 1 < dp[i * 2]:
            dp[i * 2] = dp[i] + 1

        if i * 3 <= N and dp[i] + 1 < dp[i * 3]:
            dp[i * 3] = dp[i] + 1

    print(dp[N])