[백준 2024/10/15] 1463번 1로 만들기

1. 문제

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

 

2. 접근 방법

dfs와 memoization을 이용하여 해결하면 된다고 생각하였다.

 

기존의 memoization과 다른 점이 있다면, 

3으로 나눈 것과 2로 나눈 것과 1을 뺀 것 중에 재귀적으로 답을 구한 후, 가장 작은 값을 dp에 저장해 주는 과정이다.

 

3. 코드

import sys


def dfs(n):
    if dp[n] != 0:
        return dp[n]
    ans = [sys.maxsize] * 3

    if n % 3 == 0:
        ans[0] = 1 + dfs(n//3)
    if n % 2 == 0:
        ans[1] = 1 + dfs(n//2)
    ans[2] = 1 + dfs(n-1)

    dp[n] = min(ans)
    return dp[n]


if __name__ == "__main__":
    n = int(input())
    dp = [0] * (n+3)
    dp[1] = 0
    dp[2] = 1
    dp[3] = 1

    for i in range(4, n+1):
        dfs(i)

    print(dp[n])