[백준] 16953 A->B C++

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

---

해설

A->B를 만드는 문제이다.

본인은 처음에 일단 그리디하게 A에서 어떻게 해야 최소의 연산 횟수로 B를 만들 수 있을 지 고민을 했는데 

답이 안나오더라..

 

그래서 반대로 생각해보면 A에서 B를 만들 수 있다는 것은 B에서 A로도 만들 수 있다는 것이고 그렇지 않다면 -1을 출력하면된다.

B에서 A를 그리디하게 만드는 것이다.

 

dfs, bfs로도 풀 수 있다.

우선 bfs로 푸는 경우 노드간의 가중치가 모두 동일 하다고 볼 수 있다. a * 2나 a * 10 + 1이나 비용이 1이라 할 수 있기때문에 최단거리(최소 비용)을 보장해준다. bfs도 만약 b까지 도달하지 못하면 -1을 출력하면 된다.

 

dfs로 푸는 경우 a를 2배 하는 경우, a * 10 + 1하는 두 경우로 가지를 쳐서 탐색을 진행하면된다.

a가 b보다 커지는 경우에는 예외 처리를 해주면된다.

 

그럼 dfs, bfs 시간복잡도를 분석해보자.

dfs의 경우 가지가 2갈래로 뻗어나간다. BFS와 마찬가지로, 그럼 총 노드의 수는 

2^(트리의 깊이 d) - 1이라 할 수 있다. dfs로 3번 탐색을 했다고 하자(2가지 가지로)

그럼 아래와 같은 그림이 될 것이다.

2^3 - 1 = 7개 이다.

그럼 트리의 깊이 d = logB로 대강 구할 수 있다. 만약 A가 2, B가 162인경우 대략 log162 = 7 이라는 시간 복잡도가 나온다.

 

B가 10^9라 하더라도 시간 복잡도를 초과하는 일은 없다.

 

---

코드

그리디 풀이

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int a, b; cin >> a >> b;
    int ret = 1;
    while (1) 
    {
        if (a == b) break; // 같닫면
        else if (a > b)  // a가 더 크다면 break;
        {
            ret = -1;
            break;
        }

        // b는 2로 나누어 떨어지거나 10으로 나눈 나머지가 1인 경우 둘중 하나의 경우 밖에 없다.
        if (b % 2 == 0) b /= 2;
        else if (b % 10 == 1) b = (b - 1) / 10;
        else 
        {
            ret = -1;
            break;
        }
        ret++;
    }
    cout << ret;
}

 

bfs풀이

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int a, b; cin >> a >> b;

    queue<pair<ll, ll>> q;
    q.push({1, a});
    int ret = -1;
    while (!q.empty()) 
    {
        auto cur = q.front(); q.pop();
        if (cur.second == b) 
        {
            ret = cur.first;
            break;
        }

        ll n1 = (ll)cur.second * 2;
        ll n2 = (ll)cur.second * 10 + 1;
        if (n1 <= b) q.push({cur.first + 1, n1});
        if (n2 <= b) q.push({cur.first + 1, n2});
    }
    cout << ret;
}

 

 

dfs 풀이

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// A에서 B로 변환 하는 최악의 경우 log2 (10^9) == 30 정도 이다.
// 즉 최대 30~40정도의 깊이 탐색이 필요하다.
int _min = 50; // 임의의 큰 수
ll A, B, cnt;
void dfs(ll a, int cnt)
{
    if (a > B) return;
    if (a == B) _min = min(_min, cnt);
    dfs(a * 2, cnt + 1);
    dfs(a * 10 + 1, cnt + 1);
}

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

    cin >> A >> B;
    dfs(A, 1);
    if (_min == 50) cout << -1;
    else cout << _min;
}

 

---

후기

시간 복잡도 측면에서 여러 생각을 많이 못해보았는데 여러 풀이를 보면서 도움이 되었던 문제이다.

항상 시간 복잡도도 같이 고려해서 생각을 하고 공부를 해두면 좋을거같다.