백준 1463 1로 만들기

1로 만들기 (백준 1463)

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

처음에는 top - down 방식으로 풀었는데
시간초과가 났기에,
점화식을 다시 세워본 뒤,
bottom-up 방식으로 풀었다

이후, top-down 방식의 조건을 수정하여
dp 처리 부분을 한번만 통과하도록 수정하였더니
통과하였다

Code (bottom-up)

import sys
import math

sys.setrecursionlimit(10**8)

inp = sys.stdin.readline

n = int(inp().strip())

dp = [0] + [math.inf for _ in range(n)]

dp[0] = 0
dp[1] = 0

def process(x:int):
    for i in range(2,x+1):
        v2 = v3 = math.inf
        if i % 3 == 0:
            v3 = dp[i//3]
        if i% 2 == 0:
            v2 = dp[i//2]
        
        dp[i] = min(v2 + 1,v3 + 1,dp[i-1] + 1)

    return dp[x]

print(process(n))

Code (top-down)

import sys
import math

sys.setrecursionlimit(10**8)

inp = sys.stdin.readline

n = int(inp().strip())

dp = [0] + [math.inf for _ in range(n)]

dp[1] = 0

def process(x : int)->int:
    if x <= 1:
        return 0
    
    if dp[x] != math.inf:
        return dp[x]

    sum = math.inf

    if x % 3 == 0 and x % 2 == 0:
        sum = min(process(x//3) + 1,process(x//2) + 1)
    elif x % 3 == 0:
        sum = min(process(x//3) + 1,process(x - 1) + 1)
    elif x % 2 == 0:
        sum = min(process(x - 1) + 1,process(x//2) + 1)
    else:
        sum = process(x - 1) + 1
    
    dp[x] = min(sum,dp[x])

    return dp[x]

print(process(n))

해결 아이디어

1. dp[i] : i에서 연산을 거쳐 1로 만들어지는 최소 연산 수
   
2. dp[1] = 0 (이미 1이므로)
   
3. i가 2로 나뉘면 dp[i//2]의 값을 가져오고 + 1
4. i가 3으로 나뉘면 dp[i//3]의 값을 가져오고 + 1
5. dp[i-1] 의 값을 가져오고 + 1
6. 3,4,5 과정의 값 중 가장 최소의 값을 가져오고
   dp[i]에 저장하기