[BOJ] 1463. 1λ‘ λ§λ€κΈ°(python)
πλ¬Έμ
πͺμμ΄λμ΄
1μ λΊλ€
λͺ¨λ μ μκ° 1μ΄ λκΈ° μν΄μλ 1μ λΉΌλ κ³Όμ μ λͺ¨λ μ¬μ©νλ€. 2κ° 1μ΄ λκΈ°μν΄μ 1λ², 3μ΄ 1κ° λλ €λ©΄ 2λ²(3-1-1), β¦ , nμ΄ 1λλ €λ©΄ n-1λ² 1μ λΊλ€.2λ‘ λλλ€
2λ‘ λλμ΄ λ¨μ΄μ§λ©΄ 2λ‘ λλλ κ²μ΄ 1λ‘ λλ¬νλ νμκ° μ μ΄μ§λ€. 2κ° 1μ΄ λκΈ°μν΄μ 1λ², 4κ° 2κ° λκΈ°μν΄μ 2λ²(4//2//2),β¦, n//2κ° 1μ΄ λκΈ°μν΄μ (n//2)λ² 2λ₯Ό λλλ€. μμμ 1μ λΊ νμμ 2λ₯Ό λλ νμ μ€ μ΅μκ°μ dp[n]μ λ£μ΄μ€λ€.3μΌλ‘ λλλ€
2λ²κ³Ό λμΌν μμ΄λμ΄
π₯μ½λ
1
2
3
4
5
6
7
8
9
10
11
12
import sys
input = sys.stdin.readline
n = int(input())
dp = [0]*(n+1)
for i in range(2,n+1):
dp[i] = dp[i-1]+1
if i % 2 == 0: dp[i] = min(dp[i],dp[i//2] + 1)
if i % 3 == 0: dp[i] = min(dp[i],dp[i//3] + 1)
print(dp[-1])
This post is licensed under CC BY 4.0 by the author.
Comments powered by Disqus.