[백준] 1463번 1로 만들기 - 파이썬(Python)

🗒️ 문제

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

🖥️ 풀이

# 중요포인트: 연산수만 가지고 비교함. 실제 n이 어떻게 줄어들었는지는 고려X
'''d[2]=1 (2/2)
    d[3]=1 (3/3)
    d[4]=2 (4/2 -> 2/2)
    d[5]=3 (5-1 -> 4/2 -> 2/2)
    d[6]=2 (6/3 -> 2/2) (= 1 + d[6//3])
    d[7]=3 (7-1 -> 6/3 -> 2/2) (= 1 + d[6])'''

n = int(input())
d = [0] * (n+1)

for i in range(2, n+1):
    d[i] = d[i-1] + 1 # 1 더하는 이유: 기본적으로 연산 한번은 하니까
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)# 1 더하는 이유:d리스트는 최소 "연산수" 니까(1을빼면 연산수는+1돼서)
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1) #위와 동일

print(d[n])

✔️ 참조

https://seongonion.tistory.com/40