📎 문제 출처
https://www.acmicpc.net/problem/1463
📌 문제 설명
❓ 풀이 방법
이 문제는 동적 계획법을 사용하여 간단하게 풀 수 있다.
예를 들어 5를 1로 만드는 경우를 생각해보자.
5는 2와 3으로 나누어지지 않기 때문에 1을 빼서 4로 만들고, 4는 2로 나누거나 1을 빼서 1로 만든다.
즉, (5 -> 4 -> 2 -> 1) 3번의 연산이 필요한데 이건 4를 1로 만드는 연산의 수에 1을 더한 것이라고 할 수 있다.
이처럼 주어진 수를 3으로 나눈 수와 2로 나눈 수와 1을 뺀 수 각각을 1로 만드는 데 필요한 연산의 수를 dp 테이블에 저장해두고 이 중 최솟값을 사용하면 되므로 연산의 중복을 피할 수 있다.
📌 Code
