[백준] #1463, #2193 (동적 계획법)

# 1463

바텀-업 방식의 문제 해결

import sys
input = sys.stdin.readline

N = int(input())
D = [0]*(N+1)
D[1] = 0

for i in range(2, N+1):
    D[i] = D[i-1] + 1 # -1 연산 표현 
    if i%2 == 0:
        D[i] = min(D[i], D[i//2]+1)
    if i%3 == 0:
        D[i] = min(D[i], D[i//3]+1)
    
print(D[N])

# 2193

이친수(pinary number)가 뻘하게 웃겼던 문제.

import sys
input = sys.stdin.readline

N = int(input())
D = [[0 for j in range(2)] for i in range(N+1)]

#1로 끝나는 이진수와 0으로 끝나는 이진수를 나누기 위함
#print(5) : [[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]]

D[1][1] = 1 #1자리 이친수는 한 가지만 있음
D[1][0] = 0

for i in range(2, N+1):
    D[i][0] = D[i-1][0] + D[i-1][1] # 0으로 끝나면 뒤에 0과 1이 올 수 있음
    D[i][1] = D[i-1][0] # 1로 끝나면 뒤에 0밖에 못 옴

print(D[N][0] + D[N][1])