[Python] 백준 - 1로 만들기 (동적 계획법1/1463)

문제 설명

📃 문제 링크

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력1

10

예제 출력1

3

🎈 문제 풀이

n을 1로 만드는 최소 연산 횟수를 dp[n]에 저장한다. 1부터 dp[n]까지 쭉 채워준 후 dp[n]을 출력해주면 된다.

먼저 dp[1]은 0, dp[2]는 한 번만 연산하면 되기 때문에 1, dp[3]도 1로 정해주고 시작한다. 문제의 조건 중, 2의 배수이거나 3의 배수일 때 조건이 다른데, 여기서 2의 배수이면서 3의 배수인 수를 생각해주어야 한다. 따라서 6의 배수인 수까지 네 가지 조건으로 나눠 주었다.

1을 빼는 조건은 언제나 가능하기 때문에, 각 조건에서 할 수 있는 연산과 1을 빼는 연산 중 최소값을 찾아 현재 dp[n]에 넣어준다. 쌓아가는 동안 항상 최소값을 선택하기 때문에 마지막 결과도 최소값이 될 것이다.

📝 소스 코드