백준 12852번
문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.
접근 과정
혹시 그리디한 탐색이 가능할까 시도해보았으나 최적의 방법을 찾기가 쉽지 않았다. 그래서 결국 BFS를 통한 그래프 탐색을 구현하는 것으로 방향을 바꾸어 통과하였다. 코드를 여러번 제출하면서 수정되었던 부분은 총 3가지이다.
-
처음 BFS의 구현은 습관인지 별 생각 없이 queue를 사용하여 구현하였는데, 구현 자체에는 문제가 없었지만 제출후 속도가 조금 느렸다(비교적). 거의 다익스트라 알고리즘을 구현하듯한 코드였는데 가만 고민해보니 그래프의 진행 방향이 한 방향(무조건 감소함)이기 때문에 굳이 queue를 쓸 필요가 없이 for문으로 쭉 훑는 방식으로 BFS를 구현하는게 가독성도 좋고 속도도 빨랐다.
-
다음 고려했던 부분은 시작점이다. 문제에서는 n에서 부터 시작하여 1로 이동하는 중 최소 경로이나 사실 1에서 부터 시작하여 n으로 도착하는 경우와 다를바 없다. 그런데 n에서 부터 시작할시 나눗셈을 하기 전 현재 숫자가 2나 3으로 나누어 떨어지는지 따로따로 확인 해야하지만 거꾸로 1에서 부터 시작하면 2,3을 곱한 값이 목표 지점보다 큰지만 확인하면 되기에 코드를 보다 깔끔하게 작성할 수 있었다.
-
마지막으로 고려한 것은 경로 출력하는 부분이다. DP를 통해 최단 거리만을 계산하는 것으로 끝나는게 아니라 다시금 그 경로를 복기해야 한다. 이에 대한 해결책으로 해당 노드까지 이동하는 최단 거리를 기록할 때 어떤 노드에서 왔는지 함께 기록하여 출력시 기록을 쭉 따라가며 출력하도록 구현하였다.
소스 코드
#include <cstring>
#include <iostream>
struct node_t {
int cnt;
int prev;
};
node_t nodes[1000001];
int operate(int num, int op) {
switch (op) {
case 0:
return num * 3;
case 1:
return num * 2;
case 2:
return num + 1;
default:
break;
}
return 1;
}
int main() {
std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
std::memset(nodes, -1, sizeof(nodes));
int n;
std::cin >> n;
nodes[1].cnt = 0;
nodes[1].prev = 0;
for (int cur = 1; cur < n; ++cur) {
if (nodes[cur].cnt == -1) { continue; }
int nextCnt = nodes[cur].cnt + 1;
for (int op = 0; op < 3; ++op) {
int next = operate(cur, op);
if (next > n) { continue; }
if (nodes[next].cnt == -1 || nodes[next].cnt > nextCnt) {
nodes[next].cnt = nextCnt;
nodes[next].prev = cur;
}
}
}
std::cout << nodes[n].cnt << '\n';
do {
std::cout << n << ' ';
n = nodes[n].prev;
} while (n != 0);
return 0;
}