[백준] 16953번. A → B

leeeha·2023년 1월 13일
0

백준

목록 보기
78/186
post-thumbnail
post-custom-banner

문제

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


풀이

DFS

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

int A, B; // 최대 1억 
int ans = 1e9; 

void dfs(long long num, int depth) {
	if(num > B) return; 
	if(num == B) {
		ans = min(ans, depth); // 연산의 최솟값 구하기 
		return; 
	}
	dfs(num * 2, depth + 1);
	dfs(num * 10 + 1, depth + 1);
}

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

	cin >> A >> B; 
	dfs(A, 1);

	if(ans == 1e9) cout << "-1";
	else cout << ans; 

	return 0; 
}

BFS

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

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

	int A, B; // 최대 1억 
	int ans = -1; 
	queue<pair<long long, int>> q; // 데이터 타입 주의 

	cin >> A >> B; 
	q.push({A, 1}); // 연산할 숫자, 연산한 횟수 

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

		if(num == B){ 
			ans = count; 
			break; 
		}

		if(num * 2 <= B) 
			q.push({num * 2, count + 1});

		if(num * 10 + 1 <= B)
			q.push({num * 10 + 1, count + 1});
	}

	cout << ans; 
	
	return 0; 
}

거꾸로 탐색

#include <iostream>
using namespace std;

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

	int A, B;
	cin >> A >> B;
	
	int ans = 1; 

	while(A <= B){
		if(A == B){
			cout << ans; 
			return 0; 
		}

		ans++; 
		
		if(B % 2 == 0){
			B /= 2;
		}else if(B % 10 == 1){
			B -= 1;
			B /= 10; 
		}else {
			break; 
		}
	}
	
	cout << "-1";

	return 0; 
}

profile
습관이 될 때까지 📝
post-custom-banner

0개의 댓글