1로 만들기 (feat. 백준, 1463번)

1로 만들기
https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1463
#include <iostream>
using namespace std;
int arr[static_cast<int>(1e6) + 1];
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N;
	cin >> N;
	arr[1] = 0;
	for (register int i = 2; i <= N; ++i) {
		if (i % 6 == 0)
			arr[i] = min(arr[i / 2], arr[i / 3]);
		else if (i % 2 == 0)
			arr[i] = min(arr[i - 1], arr[i / 2]);
		else if (i % 3 == 0)
			arr[i] = min(arr[i - 1], arr[i / 3]);
		else
			arr[i] = arr[i - 1];
		arr[i] += 1;
	}
	cout << arr[N] << endl;
	return 0;
}
// *&)*@*

1. 2와 3으로 모두 나누어지는 경우, / 2였던 과거 결과와 / 3이었던 과거 결과 중 작은 것에 +1이 됩니다. (6이라면 3의 결과와 2의 결과중 작은 값에 +1이 됩니다.)
2. 2로만 혹은 3으로만 나누어지는 경우, 이전 결과 또는 / 2 또는 /3의 결과 중 작은 것에서 +1이 됩니다. (8이라면 4의 결과와 7의 결과 중 작은 값에 +1이 됩니다. 4가 작은 값이라면 ×2가 되는 것이고 7이 작은 값이라면 +1이 될테니까요.)
3. 모두 해당되지 않는 경우에 대해서 이전의 결과에 +1을 취해주면 됩니다. (11이라면 2와 3으로 나누어지지 않기 때문에 10의 결과에 +1을 취하면 됩니다. 11-1이 10이니까요.)