[백준] 16953번 : A → B [C/C++]

#문제

16953번: A → B

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

16953번: A → B

 

---

#접근방법

A를 B로 바꾸려고 할 때 아래 2가지 연산을 하여 A를 B로 바꾸는데 필요한 연산의 최솟값을 구해야 한다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

자료구조 queue를 사용하여 경우의 수를 구하면 풀 수 있다.

반응형

---

#풀이

#include <stdio.h>
#include <queue>
using namespace std;

int main(){
	int A,B;
	int ans = -1;
	queue<pair<long long int,int> > q;
	
	scanf("%d %d",&A,&B);
	
	q.push(make_pair(A,1));
	
	while(!q.empty()){
		long long int k = q.front().first;
		int n = q.front().second;
		q.pop();
		
		if(k==B){
			ans = n;
			break;
		}
		
		if(k*2<=B)
			q.push(make_pair(k*2,n+1));
		if(k*10+1<=B)
			q.push(make_pair(k*10+1,n+1));
	}
	
	printf("%d",ans);
	
	return 0;
}

 

이 문제를 풀 때, queue라는 자료구조를 사용하였다. queue는 먼저 들어간 것이 먼저 나오는 형태를 가진 자료구조이다.

 

사람들이 줄을 설 때, 먼저 줄을 선 사람이 제일 먼저 서비스를 이용할 수 있는 것과 비슷한 구조이다.

 

queue라는 자료구조에 pair라는 자료형을 사용하여 2개의 수를 보관할 수 있도록 하였다.

 

먼저 q에 A와 1을 넣어주었다. 첫 번째로 들어가는 수 A는 연산하는 숫자이고, 두 번째로 들어가는 수 1은 연산을 몇 번했는지 나타내는 수이다.

 

q에서 pop으로 제일 앞에 자료를 빼고 k==B이면 n이 최소값이 되므로 ans에 n을 넣고 반복문을 중지한다.

 

1번 연산 : k*2<=B일 때, q에 (k*2,n+1)을 넣어주고

2번 연산 : k*10+1<=B일 때, q에 (k*10+1,n+1)을 넣어주어서

A가 B가 될 때까지 모든 경우의 수를 구해준다.

 

하지만 k==B가 되지 않는다면 q에 들어있는 자료는 텅 비게되므로 반복문은 종료가 된다.

 

ans를 출력하면 정답이다.

---

#성능

---

#정리

먼저 들어간 것이 먼저 나온다는 성질을 가진 자료구조 queue를 알고 있고,

 

이 자료구조의 성질을 이용하여 최소한의 연산으로 정답을 구할 수 있다는 사실을 알고 있고,

 

이를 구현할 수 있는 능력이 있으면 풀 수 있는 문제였다.