글 읽기 - 정답과 같은 로직으로 짰는데, 999999의 경우 20이 뜹니다..

whazzulookinat 5년 전 0

다른 정답지처럼, n의 경우 2로 나누어떨어지면 dp(n/2)+1, 3으로 나누어떨어지면 dp(n/3)+1, 둘다 떨어지지 않으면 dp(n-1)+1을 구해서, 셋중 가장 작은 값을 push하도록 하였습니다. 그런데 왜 testcase로 n=999999일때 20이 나오는지 이해가 가질 않습니다ㅠㅠ

#include<iostream>
#include<vector>

using namespace std;

vector<int> num;
int main(void) {
	int n; int a[3]; int min;
	cin >> n;
	int k = 3;
	num.push_back(0);//d(1)=0
	num.push_back(1);//d(2)=1
	num.push_back(1);//d(3)=1;
	while (k < n && n > 3) {
		for (int i = 0; i < 3; i++) {
			a[i] = 10000;
		}
		min = 10000;
		//cout << k << ' ' << num.back() << endl;
		if ((k + 1) % 2 == 0) {
		/*	int m = k;
			while (m % 3 == 0) {
				m = m / 3;
			}
			if (m == 1) {
				num.push_back(1 + num[k - 1]);
			}
			else {
				num.push_back(1 + num[(k + 1) / 2 - 1]);
			}*/
			a[0] = 1 + num[(k + 1) / 2 - 1];
		}
		else if ((k + 1) % 3 == 0) {
			a[1] = 1 + num[(k + 1) / 3 - 1];
		}
		a[2] = (1 + num[(k + 1) - 2]);
		for (int i = 0; i < 3; i++) {
			if (a[i] < min) {
				min = a[i];
			}
		}
		num.push_back(min);
		k++;
	}
	//for (int i = 0; i < num.size(); i++) {
	//	cout << num[i] << ' ';
	//}
	cout << num[n - 1] << endl;
	//cout << num.size();
	return 0;
}