문제

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

풀이

BFS

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

const int MAX = 1000001;
bool visited[MAX]; 

void bfs(int start){
	queue<pair<int, int>> q;
	q.push({start, 0}); // 현재 숫자, 연산 횟수 
	visited[start] = true; 

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

		if(num == 1){
			cout << cnt << endl; 
			return; 
		}

		if(num % 3 == 0 && !visited[num / 3]){ 
			q.push({num / 3, cnt + 1});
			visited[num / 3] = true; 
		}

		if(num % 2 == 0 && !visited[num / 2]){ 
			q.push({num / 2, cnt + 1}); 
			visited[num / 2] = true; 
		}

		if(!visited[num - 1]){ 
			q.push({num - 1, cnt + 1}); 
			visited[num - 1] = true; 
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	int n;
	cin >> n; 

	bfs(n); 
	
	return 0;
}

DP

dp[i] = i를 1로 만드는 데 필요한 최소 연산 횟수 (1 <= i <= n)

dp[1] = 0 부터 시작해서 i가 n이 될 때까지 1씩 늘려가며 dp 테이블을 채워나가다 보면, 결국 n을 1로 만드는 데 필요한 최소 연산 횟수를 dp[n]으로 구할 수 있다.

그리고 i에 사용할 수 있는 연산은 아래 세 가지로 제한된다.

• 1을 뺀다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• X가 3으로 나누어 떨어지면, 3으로 나눈다.

위의 연산들을 적용하여 dp[i]를 직접 구하다 보면, 이전 항들과의 규칙성을 발견할 수 있다. 이를 바탕으로 점화식을 구하면 다음과 같다.

dp[i] = dp[i - 1] + 1
if(i % 2 == 0) dp[i] = min(dp[i], dp[i/2] + 1)
if(i % 3 == 0) dp[i] = min(dp[i], dp[i/3] + 1)

이처럼 dp는 작은 문제들의 해를 모아서 큰 문제를 해결할 수 있는 최적 부분 구조를 갖고 있으며, 동일한 작은 문제를 반복적으로 해결해나간다.

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

const int MAX = 1000001; 
int dp[MAX]; 

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	dp[1] = 0; 

	int n; 
	cin >> n; 

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

	cout << dp[n]; 
	
	return 0;
}

BFS로 푸는 게 시간과 메모리가 더 절약되는 거 같다.