1로 만들기 ( 1463 번 )

1463번: 1로 만들기

 

---

🧠 알고리즘

• DP (Dynamic Programming, 동적 계획법)

 

✔️ 동작 방식

문제 핵심 아이디어
주어진 수 n을 1로 만드는 최소 연산 횟수를 구하는 문제이다.
가능한 연산은 다음 세 가지이다.

• n → n - 1
• n → n / 2 (단, 2로 나누어떨어질 때만 가능)
• n → n / 3 (단, 3으로 나누어떨어질 때만 가능)

이때, 각 수 i를 1로 만드는 최소 연산 횟수 dp[i]를 구할 때
더 작은 문제(i-1, i//2, i//3)의 결과값을 이용하는 점화식 기반 DP를 사용한다.

---

 

🧾 코드

import sys

def _main(n):
    dp = [0] * (n + 1)

    for num in range(2, n + 1):
        dp[num] = dp[num - 1] + 1

        if num % 3 == 0:
            dp[num] = min(dp[num], dp[num // 3] + 1)

        if num % 2 == 0:
            dp[num] = min(dp[num], dp[num // 2] + 1)

    return dp[n]


n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

for num in range(2, n + 1) : 각 수를 순회하며 비교 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )