[백준][C++] 1463: 1로 만들기

문제 링크: https://www.acmicpc.net/problem/1463

 

다이나믹 프로그래밍 문제입니다. top-down, bottom-up 두 방식으로 풀어봤습니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;
int dp[1000001];

int solve(int x) {
	if (x == 1)
		return 0;
	
	int& ret = dp[x];
	if (ret != -1) return ret;
	ret = INF;
	
	if (x % 3 == 0) ret = min(ret, solve(x / 3) + 1);
	if (x % 2 == 0) ret = min(ret, solve(x / 2) + 1);
	ret = min(ret, solve(x - 1) + 1);

	return ret;
}

int main()
{
#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

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

	int n;
	cin >> n;
	cout << solve(n) << '\n';

	return 0;
}

탑다운 방식으로 푼 소스입니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


int dp[1000001];

int solve(int x) {
	dp[1] = 0;

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

	return dp[x];
}

int main()
{
#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);


	int n;
	cin >> n;
	cout << solve(n) << '\n';

	return 0;
}

바텀업 방식으로 푼 소스입니다.

함수 호출스택때문일까요. 이 문제는 탑다운 방식이 메모리도 많이 먹고 좀 더 느리게 나왔네요.