Post

[BOJ] 1463. 1둜 λ§Œλ“€κΈ°(python)

πŸ“Œλ¬Έμ œ

Alt text

πŸ’ͺ아이디어

  1. 1을 λΊ€λ‹€
    λͺ¨λ“  μ •μˆ˜κ°€ 1이 되기 μœ„ν•΄μ„œλŠ” 1을 λΉΌλŠ” 과정은 λͺ¨λ‘ μ‚¬μš©ν•œλ‹€. 2κ°€ 1이 λ˜κΈ°μœ„ν•΄μ„œ 1번, 3이 1κ°€ 되렀면 2번(3-1-1), … , n이 1되렀면 n-1번 1을 λΊ€λ‹€.

  2. 2둜 λ‚˜λˆˆλ‹€
    2둜 λ‚˜λˆ„μ–΄ 떨어지면 2둜 λ‚˜λˆ„λŠ” 것이 1둜 λ„λ‹¬ν•˜λŠ” νšŸμˆ˜κ°€ 적어진닀. 2κ°€ 1이 λ˜κΈ°μœ„ν•΄μ„œ 1번, 4κ°€ 2κ°€ λ˜κΈ°μœ„ν•΄μ„œ 2번(4//2//2),…, n//2κ°€ 1이 λ˜κΈ°μœ„ν•΄μ„œ (n//2)번 2λ₯Ό λ‚˜λˆˆλ‹€. μ•žμ—μ„œ 1을 λΊ€ νšŸμˆ˜μ™€ 2λ₯Ό λ‚˜λˆˆ 횟수 쀑 μ΅œμ†Ÿκ°’μ„ dp[n]에 λ„£μ–΄μ€€λ‹€.

  3. 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.