1. 문제
백준1463
2. 설명
3. 접근
2->1
3->1
4->2->1
5->4->2->1
6->2->1 / 6->3->1 / 6->5->4->2->1 : 2와3으로 나눠지는 수는 2나 3중에 하나의 경우만 생각하면 되고 여기서는 1을 뺀 경우가 연산횟수가 많아서 반대의 경우를 찾을 경우를 생각했습니다.
...
10->5->4->2->1 / 10->9->3->1 : 이 경우에 1을 뺀 경우가 연산횟수가 적었습니다.
큰 문제를 작은 문제로 나누어 풀어야해서 dynamic programming과 divde and conquer을 떠올렸지만, 5일 경우 4->2->1을 구해야하고 10일때도 5->4->2->1을 구해야합니다. 이런식으로 작은 부분문제들이 반복되어 나타나서 dynamic programming을 생각했습니다. dp방식중에 bottom-up 방식을 사용하여 시간복잡도 O(n)으로 해결할 수 있습니다.
4. 코드
#include <iostream>
#include <algorithm>
using namespace std;
void make_one(int* arr, int N);
int main() {
int arr[1000001] = { 0 };
int N = 0;
cin >> N;
make_one(arr, N);
cout << arr[N];
}
void make_one(int* arr, int N) {
int i = 0;
arr[1] = 0;
for (i = 2; i < N+1; i++) {
arr[i] = arr[i - 1] + 1;
if (i % 2 == 0) { arr[i] = min(arr[i], arr[i / 2] + 1); }
if (i % 3 == 0) { arr[i] = min(arr[i], arr[i / 3] + 1); }
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준2193] 이친수 (C++) (0) | 2021.01.07 |
---|
댓글