[BOJ] 1463번: 1로 만들기

문제 링크

https://www.acmicpc.net/problem/1463

접근한 방식

dp로 접근하였다.
n이 작을때의 상황들로부터 시작하여, n이 3으로 나누어떨어지는지 2로 나누어떨어지는지 등으로 조건을 나누어 1로 만드는 경우의 수가 제일 작아지게 만든다.

탑다운, 바텀업으로 풀어보았다.

코드

C++

#include <iostream>
#include <algorithm>
#define endl '\n'

using namespace std;

int N;
int savedData[1000001];

int topDown(int n) {
	if (savedData[n])
		return savedData[n];
	if (n == 1)
		return 0;

	if (n % 3 == 0 && n % 2 == 0)
		return savedData[n] = min(min(topDown(n / 3), topDown(n / 2)), topDown(n - 1)) + 1;
	else if (n % 2 == 0)
		return savedData[n] = min(topDown(n / 2), topDown(n - 1)) + 1;
	else if (n % 3 == 0)
		return savedData[n] = min(topDown(n / 3), topDown(n - 1)) + 1;
	else
		return savedData[n] = topDown(n - 1) + 1;
}

int bottomUp(int n) {
	int data[1000001];
	data[1] = 0;

	for (int i = 2; i <= n; i++) {
		data[i] = data[i - 1] + 1;
		
		if (i % 2 == 0 && data[i] > data[i / 2] + 1)
			data[i] = data[i / 2] + 1;
		if (i % 3 == 0 && data[i] > data[i / 3] + 1)
			data[i] = data[i / 3] + 1;
	}

	return data[n];
}

int main() {
	cin >> N;

	cout << bottomUp(N) << endl;

	return 0;
}