백준 1463 : 1로 만들기

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

1. 접근

• 처음에는 최솟값을 구해야 하고, 그때의 연산이 3종류이기 때문에 단순하게 BFS를 이용해서 풀었다.
• 구하고나서 보니, 구하는 경로값이 필요한 경우가 아니고, 연산 값들이 연속적이었기 때문에 DP를 이용할 수 있다는 것을 깨달았다.
  (n값을 1로 만든다고만 생각했는데, 거꾸로 1부터 n까지 가는 과정을 생각하지 못했다)
• dp 배열에 각각의 연산값을 쓰고, n번째 값까지 dp 과정을 반복해주면 된다.
• t번의 경우의 수를 구해야 하는 문제였다면 dp가 훨씬 효율적일 것이고, 경로를 구해야했다면 BFS가 더 효율적이었을 것 같다.

2. 나의 풀이

1) BFS

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int ret = -1;

void BFS(int num) {
	queue < pair<int, int>> q;
	q.push(make_pair(num, 0));

	while (!q.empty()) {
		int num = q.front().first;
		int count = q.front().second;
		q.pop();

		if (num == 1) {
			ret = min(ret, count);
			return;
		}

		if (num % 3 == 0)	q.push(make_pair(num / 3, count + 1));
		if (num % 2 == 0)	q.push(make_pair(num / 2, count + 1));
		q.push(make_pair(num - 1, count + 1));
	}
	
	return;
}

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

	int n;
	cin >> n;
	ret = n;

	BFS(n);
	cout << ret << "\n";
	return 0;
}

2) DP

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;

	vector<int> dp(n+1);
	dp[1] = 0;

	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]<<"\n";
	return 0;
}

3. 채점 값 비교

위의 채점 결과가 DP.
DP 가 훨씬 빠르고 메모리적으로 효율적인 것을 알 수 있다.