C++ 백준 1463번

백준 1463번 www.acmicpc.net/problem/1463

1463번: 1로 만들기

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

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

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

 

다이나믹 프로그래밍에 대해서 계속 풀어보려고 한다.

쉬운 다이나믹 프로그래밍은 그냥 문제에 있는걸 바로 점화식으로 생각해보면 된다!!

Top-Down 방식과 Bottom-up 방식 두가지로 풀었다.

#include<iostream>
using namespace std;
int d[1000000];
/* Top-down 방식
 int go(int n) {
	if (n == 1) return 0;
	if (d[n] > 0) return d[n]; // memoization
	d[n] = go(n - 1) + 1; // 일단 -1 한거 저장
	if (n % 2 == 0) {
		int temp = go(n / 2) + 1; // 2로 나눠지면 -1한거랑 뭐가더 작은지 비교!
		if (d[n] > temp) d[n] = temp;
	}
	if (n % 3 == 0) {
		int temp = go(n / 3) + 1; // 3으로 나눠지면 -1한거or 2로도 나눠져서 저 위에서 한번더 비교된거랑 다시 비교!!
		if (d[n] > temp) d[n] = temp;
	}
	return d[n];
}
*/

// Bottom-up 방식
int go(int n) {
	d[1] = 0;
	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0 && d[i] > d[i / 2] + 1) {
			d[i] = d[i / 2] + 1;
		}
		if (i % 3 == 0 && d[i] > d[i / 3] + 1) {
			d[i] = d[i / 3] + 1;
		}
	}
	return d[n];
}

int main() {
	int t;
	cin >> t;
	cout << go(t) << '\n';
}