[백준] 1463 - 1로 만들기 (Python)

문제 링크

알고리즘

• 다이나믹 프로그래밍

풀이

처음엔 dfs 방식으로 풀었다가 가볍게 시간초과가 나버렸다.

결국 다이나믹 프로그래밍으로 이 문제를 해결했다.

다이나믹 프로그래밍은 위에서부터 아래로 재귀적으로 내려오는 햐향식과
아래서부터 Memorize를 이용해서 거꾸로 올라가는 상향식이 있다.

이 문제는 상향식으로 해결했다.

먼저 memo 변수에 0 * N 만큼 채워진 리스트를 선언한다.
이 리스트에는 각 인덱스마다 도착하는데 걸리는 횟수를 저장한다.

이제 for문에서 1씩 올라가면서 세 경우에 대해 모두 계산한 뒤 제일 적게 걸리는 횟수를 저장한다.

마지막으로 N에 해당하는 인덱스를 memo에서 꺼내면 된다.

(N으로 10이 주어졌을 때 마지막 memo의 모습)
[0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]

코드

# 다이나믹 프로그래밍
# 위에서부터 계산하는 방식이 아닌 아래서부터 메모하면서 올라가는 상향식

N = int(input())

memo = [0] * (N + 1)  # 단계를 올라가면서 1까지 가는 경로의 최솟값을 저장

for i in range(2, N + 1):
    # 먼저 N-1을 계산
    memo[i] = memo[i - 1] + 1
    # 예를 들어 i=9면 8+1로 가는게 빠른지 3*3으로 가는게 빠른지 계산
    if i % 3 == 0:
        memo[i] = min(memo[i], memo[i // 3] + 1)
    if i % 2 == 0:
        memo[i] = min(memo[i], memo[i // 2] + 1)
print(memo[N])