(BOJ)1463 1로 만들기

for문을 이용한 방식

int n, dp[1000001];


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;

	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if(i%3==0) dp[i] = min(dp[i], dp[i / 3] + 1);
		if(i%2==0) dp[i] = min(dp[i], dp[i / 2] + 1);
	}
	cout << dp[n];
	return 0;
}

 

메모리: 5892KB

시간: 4ms

 

 

 

재귀로 푼 방식

int n, dp[1000001];

int func(int a) {
	if (a == 1) return 0;
	int &ret = dp[a];
	if (ret != -1) return ret;

	ret = func(a - 1)+1;
	if (a % 3 == 0) ret = min(ret, func(a / 3)+1);
	if (a % 2 == 0) ret = min(ret, func(a / 2)+1);

	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;

	memset(dp, -1, sizeof(dp));

	cout << func(n) << '\n';
	return 0;
}

메모리: 37020KB

시간: 32ms

 

* system("pause"); 써서 런타임에러남 헤헤