[백준]동적 계획법1/1로 만들기/1463 풀이 JAVA

문제

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

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

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

 

입력

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

 

출력

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

 

 

풀이 (JAVA)

dp는 각 인덱스가 1이 되기 위한 최소 연산 횟수를 갖고 있다.

(dp[N] = m; : N을 1로 만들기 위한 최소 연산 횟수 = m)

 

dp배열은 규칙이 없기 때문에 이렇게 일일이 최솟값을 비교해서 구해야 한다.

 

N이 6으로 나눠지면

dp[N / 3], dp[N / 2], dp[N - 1]중 최솟값을 알아내어 그렇게 연산한 횟수 1을 더해 dp[N]에 저장

다음도 마찬가지로

N이 3으로 나눠지면

dp[N / 3], dp[N - 1]중 최솟값을 알아내어 1을 더해 dp[N]에 저장

N이 2로 나눠지면

dp[N / 2], dp[N - 1]중 최솟값을 알아내어 1을 더해 dp[N]에 저장

그렇지 않다면

dp[N - 1]을 하고 1을 더해 dp[N]에 저장한다.

 

처음엔... dp[0]~dp[N]까지의 규칙을 찾아보려 했다.

근데 규칙 찾는 문제가 아니어서 좀 헤맸다.

규칙 없는 문제는 이렇게 푸는구나~~~