백준 BOJ 16397 - 탈출

DP + BFS 문제.

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

16397번: 탈출

 

dp[k] 를 숫자 $K$를 만드는데 필요한 최소한의 버튼 누름 횟수 라고 하고,

숫자 $K$인 상태에서 두 버튼을 눌렀을때 변화하는 수를 각각 $A(K)$, $B(K)$ 이라고 하면

 

dp[A(K)] = dp[k] + 1

dp[B(K)] = dp[k] + 1

이 된다.

 

버튼 A, B를 누를 때 각각 숫자가 99,999를 넘어가는 경우에 대한 처리가 필요함에 유의.

만들어진 dp는 B(K) 버튼을 눌렀을때 수가 작아질 수도 있다는 특성 때문에

상향식 방식으로 구현하기에 어려움이 좀 있고,

깔끔하게 BFS로 구현해서 풀었다.

 

그냥 방문처리만 하는 BFS로도 문제를 해결할 수 있을듯 싶은데,

나는 개인적으로는 방문처리용 배열을 만드느니 DP로 짜는걸 선호해서

DP로 풀어보았다.

#include <bits/stdc++.h>
#define MAX 998244353
using namespace std;

int dp[123456] = {0};
// dp[k] : 숫자 K를 만드는데 필요한 최소한의 버튼누름 횟수. 

int A(int k){
	if(k+1 > 99999) return -1;
	return k+1;
}

int B(int k){
	if(k == 0) return k;
	k *= 2;
	
	if(k > 99999) return -1;
	
	int tmp = 1;
	for(int i=k; i>=10; i/=10) tmp *= 10;
	return k-tmp;
}

void bfs(int k){
	for(int i=0; i<123456; i++) dp[i] = MAX;
	
	int a,b;
	queue<int> q;
	q.push(k);
	dp[k] = 0;

	while(!q.empty()){
		int now = q.front();
		q.pop();
		
		a = A(now);
		b = B(now);
		
		if(a != -1 && dp[a] == MAX){
			dp[a] = dp[now]+1;
			q.push(a);
		}
		if(b != -1 && dp[b] == MAX){
			dp[b] = dp[now]+1;
			q.push(b);
		}
	}
	return;
}

int main(){
	int N,T,G;
	cin >> N >> T >> G;
	
	bfs(N); // N -> G;
	int ans = dp[G];
	
	if(ans == MAX || ans > T) cout << "ANG";
	else cout << ans;
	return 0;
}