[백준 알고리즘] 1463번 1로 만들기

문제

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

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세개를 적절히 사용해서 1을 만들려고 한다. 

연산을 사용하는 횟수의 최소값을 출력하시오.

힌트

10의 경우에 10->9->3->1로 3번 만에 만들 수 있다.

풀이

10이 들어왔을 경우를 보면 2,3 연산을 사용할 수 있지만 3번째 연산을 선택해서 9로 만든다. 만약 2번째 연산을 고르면 10->5->4->2->1 로 연산횟수가 늘어난다. 

따라서 n이 값을 재귀적으로 줄여나가는 방법보다 DP를 사용해야한다

점화식을 세워보면....(세운걸 찾아보니)

f(n)

=

0 -> n=1 일때

min (f(n/3)+1(n이 3의 배수일때), f(n/2)+1(n이 2의 배수일때), f(n-1)+1) 이다

 

코드

dp[1]=0;

for(i=2; i<=n; i++)

{

if(i%3 == 0 && i%2 == 0)

dp[i]=MIN(dp[i-1]+1,MIN(dp[i/3]+1, dp[i/2]+1));

else if(i%3 == 0)

dp[i]=MIN(dp[i/3]+1, dp[i-1]+1);

else if(i%2 == 0)

dp[i]=MIN(dp[i/2]+1, dp[i-1]+1);

else

dp[i]=dp[i-1]+1;

}

더 깔끔하게 짜보고싶었는데...

3이랑 2랑 둘다 나눠질 때 6같은 경우에 어떻게 처리할지 생각이 잘 안난다...