문제
풀이
top-down(bfs) 방식으로 구현하다가, bottom-up 방식으로 바꿔 풀었다. n까지 도달하기 위해 걸린 cnt를 저장하고 있는 dp배열을 이용하여 1부터 시작하여, 기존 값과 비교하여, 새로 구한 값이 더 작으면 dp값에 넣는 식으로 코드가 진행된다. 이 때, before함수를 통해 그 전의 값들이 먼지 역추적을 하게끔 저장되어 있다. 이들을 각각 정답에 맞게 출력해준다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N;
scanf("%d", &N);
vector<int> dp(N+1);
vector<int> before(N+1);
dp[1] = 0;
for(int i = 2; i<=N; i++){
dp[i] = dp[i-1] + 1;
before[i] = i-1;
if(i%2 == 0 && dp[i] > dp[i/2] + 1){
dp[i] = dp[i/2] + 1;
before[i] = i/2;
}
if(i%3 == 0 && dp[i] > dp[i/3] + 1){
dp[i] = dp[i/3] + 1;
before[i] = i/3;
}
}
printf("%d\n", dp[N]);
printf("%d ", N);
int index = N;
int x;
while(1){
x = before[index];
if(x == 0) break;
printf("%d ", x);
index = x;
}
}
