[백준 1463] 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

2023.04.14 - [코딩 테스트/개념] - dynamic programming

# 1 ≤ N ≤ 10^6

import sys

readline = sys.stdin.readline

N = int(readline())

# d[n] = 숫자 n이 1이 될 때까지 필요한 연산 횟수의 최솟값
# d[i] = min(d[i // 3] + 1, d[i // 2] + 1, d[i - 1] + 1)
# 초기화: d[1] = 0
d = [0 for _ in range(N + 1)]

# bottom-up
for i in range(2, N + 1):
    if i % 3 == 0 and i % 2 == 0:
        d[i] = min(d[i // 3] + 1, d[i // 2] + 1, d[i - 1] + 1)
    elif i % 3 == 0:
        d[i] = min(d[i // 3] + 1, d[i - 1] + 1)
    elif i % 2 == 0:
        d[i] = min(d[i // 2] + 1, d[i - 1] + 1)
    else:
        d[i] = d[i - 1] + 1

print(d[N])

위 방식은 bottom-up 방식이다. 문제에서 물어보는 n이 1이 될 때까지 필요한 연산 횟수의 최솟값을 d[n]이라 정했다. 그러면 최솟값이 되는 가능한 경우가 3가지 있는데, 그 중에서 가장 작은 값을 고르면 d[n]이 된다. 일반화한 점화식은 주석에 작성했다.

top-down 방식은 아래와 같이 재귀함수로 구현할 수 있다.

# 1 ≤ N ≤ 10^6

import sys

readline = sys.stdin.readline

N = int(readline())

# d[n] = 숫자 n이 1이 될 때까지 필요한 연산 횟수의 최솟값
# d[i] = min(d[i // 3] + 1, d[i // 2] + 1, d[i - 1] + 1)
# 초기화: d[1] = 0
d = [-1 for _ in range(N + 1)]
d[1] = 0

# top-down
def find_min_count(i):
    if d[i] != -1:
        return d[i]

    if i % 3 == 0 and i % 2 == 0:
        d[i] = min(
            find_min_count(i // 3) + 1,
            find_min_count(i // 2) + 1,
            find_min_count(i - 1) + 1,
        )
    elif i % 3 == 0:
        d[i] = min(find_min_count(i // 3) + 1, find_min_count(i - 1) + 1)
    elif i % 2 == 0:
        d[i] = min(find_min_count(i // 2) + 1, find_min_count(i - 1) + 1)
    else:
        d[i] = find_min_count(i - 1) + 1

    return d[i]


print(find_min_count(N))