1로 만들기 풀이

문제 링크: https://www.acmicpc.net/problem/1463

백준 알고리즘 기초 1/2 400에서 1번째 - 1463번 1로 만들기를 풀어보았다.

 

풀이: 0부터 n까지 메모이제이션을 적용했다.

 

C++

 

Python

n=int(input())
arr=[0 for i in range(n+1)]
for i in range(2,n+1):
	arr[i]=arr[i-1]+1
	if i%2==0: arr[i]=min(arr[i],arr[i//2]+1)
	if i%3==0: arr[i]=min(arr[i],arr[i//3]+1)
print(arr[n])

Java