#16953 A→B

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

16953번: A → B

실버 1의 문제이다. 이왜그? 이게 왜 그리디 문제인가? 그리디라기 보다 bfs문제라고 하는게 맞는것같다. 아무튼 참신한 문제인 것 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 100000001
using namespace std;

int a,b;
queue<pair<long long,int>> q;

int main()
{
  //freopen("input.txt","r",stdin);
  cin>>a>>b;
  int ans=-1;
  q.push(make_pair(a,1));
  while(!q.empty()){
    long long x=q.front().first;
    int cnt=q.front().second;
    q.pop();

    if(x==b){
      ans=cnt;
      break;
    }
    if(2*x<=b)
      q.push(make_pair(2*x,cnt+1));
    if(10*x+1<=b)
      q.push(make_pair(10*x+1,cnt+1));
  }
  cout<<ans;
}

문제를 처음 봤을때 그냥 막막했다. 손으로 끄적여보다가 곱하기 2와 곱하기10 +1 이렇게 두가지가 있는걸 보고 문득 떠올랐다. 숨바꼭질3 문제와 굉장히 유사하다. 물론 이문제는 가중치가 1로 똑같다. 하지만 bfs를 사용하여 코드를 구현할 수 있을 것 같았다. 처음에 내가 작성한 코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 100000000
using namespace std;

int a,b;
vector<int> dist(MAX);
vector<int> visited(MAX);
queue<int> q;

void bfs(int x){
  q.push(x);
  visited[x]=1;
  while(!q.empty()){
    int now=q.front();
    q.pop();
    if(10*now+1<=b){
      q.push(10*now+1);
      visited[10*now+1]=1;
      dist[10*now+1]=dist[now]+1;
    }
    if(2*now<=b){
      q.push(2*now);
      visited[2*now]=1;
      dist[2*now]=dist[now]+1;
    }
  }
}

int main()
{
  //freopen("input.txt","r",stdin);
  cin>>a>>b;
  bfs(a);
  cout<<dist[b]+1;
}

그냥 배열을 쓰면 MAX가 1억이기때문에 메모리초과가 날 것을 예상하여 vector을 사용했다. 지금보니까 사실 visited 벡터는 없어도 되는 것 같다.

아무튼 1번과정(2곱하는것)과 2번과정(뒤에 1을 붙이는것)을 했을때, 원하는 수, 즉 b보다 작거나 같다면 계속 과정을 반복하도록 했다. 그리고 dist라는 벡터에는 연산횟수를 넣어주었다.

이렇게 제출하니 메모리초과가 나왔다. 벡터를 사용하면 될줄 알았는데 안됐다.(왜지 ㅠ)

 

아무튼 원래 정답코드로 돌아가서,,

queue를 pair로 만들었는데, first에는 연산하게될 숫자를, second에는 연산횟수를 넣어두었다. long long형으로 한 이유는 연산하려는 수가 10억(MAX)일때 뒤에 1을 붙이는 과정을 진행하면 100억이상이 되어 int형을 벗어나는 수가 될 수도 있기 때문이다.