[알고리즘] BOJ 1463번 / 1로 만들기

문제

 

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

 

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

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

3. 1을 뺀다.

 

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

 

입력

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

 

출력

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

 

예제 입력 1                         예제 출력 1

2                                          1

 

예제 입력 2                         예제 출력 2

10                                        3

 

힌트

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

 

---

 

DP는 시간제한이 작기 때문에 무작정 생각나는 대로 문제를 진입하는 것보다는
어떻게 하면 효율적이면서 시간 복잡도를 줄일 수 있을지 생각하면서 문제를 푸는 것이 맞는 것 같다.
이 문제는 입력 숫자 최대가 매우 크기 때문에 k=1부터 시작해 저장해가면서 올라가게 풀어보았다.

일정한 규칙이 있기 때문에 점화식을 생각해 보았다.
d[k]라는 테이블을 만들고 k=1 일 때 0이기 때문에 d[1] = 0
초깃값은 1개 나오는 것 같았다.

도출해 낸 점화식은 아래와 같다.

for(int i = 2; i <= n; i++) {
    d[i] = d[i-1] + 1;
    if(i % 2 == 0) d[i] = min(d[i], d[i/2] + 1);
    if(i % 3 == 0) d[i] = min(d[i], d[i/3] + 1);
}

d[i]에서 +1을 해 1을 뺀 횟수를 먼저 세주고
2 또는 3으로 나누어떨어질 때랑 비교해서 최솟값을 d[i]에 저장해 주고 올라가면서 우리가 원하는 n까지 도달하게 했다.