Make it 1 / 1로 만들기 [BOJ 1463]

Code:

import sys
read = sys.stdin.readline

def one(a, N):
    for i in range(2, N+1):
        
        a[i] = a[i-1] + 1
        
        if i % 3 == 0:
            a[i] = min(a[i//3] + 1, a[i])
        if i % 2 == 0:
            a[i] = min(a[i//2] + 1, a[i])
            
    return a[N]
    
N = int(read())

a = [0 for _ in range(N+1)]

ans = one(a, N)
print(ans)

We import system. We save sys.stdin.readline into the read variable.

import sys
read = sys.stdin.readline

We make a function called one and take the input of a and N. The equation for this question is going to be:

	a = min(a//2, a//3, a-1) + 1

So we use this code to decribe the equation.

        a[i] = a[i-1] + 1
        
        if i % 3 == 0:
            a[i] = min(a[i//3] + 1, a[i])
        if i % 2 == 0:
            a[i] = min(a[i//2] + 1, a[i])

So this is the function

def one(a, N):
    for i in range(2, N+1):
        
        a[i] = a[i-1] + 1
        
        if i % 3 == 0:
            a[i] = min(a[i//3] + 1, a[i])
        if i % 2 == 0:
            a[i] = min(a[i//2] + 1, a[i])
            
    return a[N]

We get input of N. We use list comprehension to make 0 increase by 1 everytime. It is stored in the variable a. We then store the function in a variable called ans and print ans.

N = int(read())

a = [0 for _ in range(N+1)]

ans = one(a, N)
print(ans)