12851

해결방법

BFS를 활용하여 쭉 순회하면서 이미 방문한 숫자도 depth가 같은 경우 경우의 수를 추가하면 된다.

굳이 depth를 저장할 필요없이 훨씬 간단하게 구현할 수 있는데 안했다.....

초심 잃은 것인가.....

아 그리고 굳이 범위인 100000 보다 크게 잡을 필요는 없다. 왜냐하면 v*2를 해서 10만 보다 큰 값에서 감소하는 것보다 (v-1) * 2와 같이 감소하고 곱하는 것이 depth가 반가량 감소하게 되기 때문이다.

나중에 좀 간소하게 짜도록 노력하자.....

시간 복잡도는 O(N) 

왜냐하면 중복 숫자는 큐에 집어 넣지 않기 때문에~~

공간 복잡도는 O(N) 

방문과 숫자를 카운트하기 위해서~~~

 

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

int visit[133334],cnt[133334];

int main (){

freopen("sample.txt","r",stdin);

int N, K; 

scanf("%d %d", &N, &K);

memset(visit, -1, sizeof(visit));

queue<pair<int,int> > que;

que.push(make_pair(N,0));

visit[N] = 0;

cnt[N] = 1;

while(!que.empty()){

pair<int,int> v = que.front();

que.pop();

if(visit[K]!=-1&&visit[K]<v.second) break;

if(v.first<K && visit[v.first+1] == -1){

visit[v.first+1] = visit[v.first] + 1;

cnt[v.first+1]+=cnt[v.first];

que.push(make_pair(v.first+1,v.second+1));

}

else if(v.first<K && visit[v.first+1]==v.second+1)

cnt[v.first+1]+=cnt[v.first];

if(v.first-1 >= 0 && visit[v.first-1] == -1){

visit[v.first-1] = visit[v.first] + 1;

cnt[v.first-1]+=cnt[v.first];

que.push(make_pair(v.first-1,v.second+1));

}

else if(v.first-1 >= 0 && visit[v.first-1]==v.second+1)

cnt[v.first-1]+=cnt[v.first];

if((v.first<<1) < 133334 && visit[v.first<<1] == -1){

visit[v.first<<1] = visit[v.first] + 1;

cnt[v.first<<1]+=cnt[v.first];

que.push(make_pair(v.first<<1,v.second+1));

}

else if((v.first<<1) < 133334 && visit[v.first<<1]==v.second+1)

cnt[v.first<<1]+=cnt[v.first];

}

printf("%d\n%d\n", visit[K],cnt[K]);

return 0;

}