[Silver III] 1로 만들기 - 1463

문제 링크

성능 요약

메모리: 173364 KB, 시간: 1284 ms

분류

다이나믹 프로그래밍

코드 분석

내 코드 :

N = int(input())
dp = [0]+[*range(3*10**6)]
for i in range(N):
    dp[i*2] = min(dp[i]+1, dp[i*2])
    dp[i*3] = min(dp[i]+1, dp[i*3])
    dp[i+1] = min(dp[i]+1, dp[i+1])

print(dp[N])

3*10**6까지 기록할 수 있는 dp 테이블을 만들고, N-1까지 순회하며 다음 단계를 기록해나간다. 목표지점인 dp[N]을 출력. i*2에 대해선 N//2까지만 순회해도 되고, i*3에 대해서도 마찬가지로 N//3까지만 순회해도 된다. 이를 보정하면 시간을 단축할 수 있다고 예상된다.

anfdjqkd 님의 코드 :

import sys
d = {1: 0, 2: 1}
def s(n: int) -> int:
    if n in d:
        return d[n]
    t = 1 + min(s(n // 3) + n % 3, s(n // 2) + n % 2)
    d[n] = t
    return t
print(s(int(sys.stdin.readline())))

메모리 약 31MB, 시간 36ms

동적 계획법보다 빠른 재귀함수다.
1. 딕셔너리 d를 캐시로 사용했다.
2. n을 2나 3으로 나눈 몫에 s를 실행한 값은 n보다 작은 2나 3으로 나누어떨어지는 어떤 수에서 n을 2나 3으로 나눈 나머지를 더한 만큼 이동해 실행한 것과 같다. 예를 들어 n이 17일 때, d[17]에 기록될 값은, d[16]+1 이거나 d[15]+2이다. n을 2나 3으로 나눈 나머지는 1씩 빼서 이동했다는걸 뜻한다. 마찬가지로 n이 3일 때에는 s(3)이 실행되고 1 + min(s(1)+0, s(1)+1)이 실행된다. 각각 3에서 3을 나눠 1로 가는 경우와, 2로 1칸 이동해 2를 나누는 경우를 나타낸다.
3. 딕셔너리를 사용해 아래에서 위로 올라오고 재귀함수로 밑에서 아래로 내려간다.