[백준] 1463번: 1로 만들기

 

 

🔍 문제 읽기

1463번: 1로 만들기

 

입력	출력
정수 N	정수 N의 연산을 사용하는 횟수의 최솟값

 

 

💡풀이

❗️[핵심] DP 다이나믹 프로그래밍

초기값

d[1] = 0

 

점화식 

① 3으로 나누어 떨어짐 ➡︎ d[k] = d[k/3]+1

② 2로 나누어 떨어짐 ➡︎ d[k] = d[k/2]+1

③ 1을 빼면 ➡︎ d[k] = d[k-1]+1

①, ②, ③ 중 최솟값

 

 

🧩코드