[백준1463] 1로 만들기 (C++)

1. 문제

백준1463

www.acmicpc.net/problem/1463

1463번: 1로 만들기

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); }	
	}
}