백준 알고리즘 - 1463(DP)

백준 알고리즘 1463

문제:

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

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

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

입력: 

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

풀이:    Dp[i]   =   1) Dp[i/3] + 1

                              2) Dp[i/2] + 1

                              3) Dp[i-1] + 1     (뒤 숫자 +1은 연산 횟수를 증가 시켜준다.)

 

1을 만들기 위해 사용되는 방법은 총 3가지로 3으로 나누거나 2로나누거나 1을 빼는 것이다.

만약 정수 10이 주어졌다면  1로 만드는 과정을 하기 위해 가장 작은 정수 1부터 1로 만드는 연산횟수를 구한다. 

i가 반복문에 사용되는 정수이며 1로 만드는 횟수는 Dp[1] 로 표현한다.

그러므로 Dp[1] = 1; 값이 들어가게 된다. 

Dp[2]도 2를 1로 만드는 과정은 2로 나누면 1로 변하기에 Dp[2] = 1; 로 표현할 수 있다.

코드를 살펴보면 Dp[i]의 기본 값으로 Dp[i] = Dp[i] - 1로 설정한다.

그 후 for 반복문을 통해 2로 나누어졌을 때 Dp[i/2] + 1 과 Dp[i] (이놈은 Dp[i] = Dp[i-1] + 1) 을 비교해 더 적은 연산횟수를 가진 쪽 을 택한다. 3으로 나누어졌을 때도 마찬가지이다.

반복문 후에 알고자하는 정수의 연산횟수 Dp[N]을 출력한다.

코드

느낀점 : 동적계획 알고리즘이 다시 사용되는 계산되는 값을 배열에 담고 다시 사용하는 것 같은데 점화식을 어떻게 구하는지 어렵다.  c++은 메모라이징인가 이상한 기술이 있던데 사용해봐야겠다.