Level 2. 숫자 변환하기

Level 2. 숫자 변환하기

 

 

첫 번째 시도에서는 정답이었으나 시간 초과가 발생했다.

 

값이 아니라 연산 횟수가 적은 순으로 BFS를 수행하다보니 그런 것 같다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int solution(int x, int y, int n)
{
    auto op1 = [n](int x) { return x + n; };
    auto op2 = [ ](int x) { return x + x; };
    auto op3 = [ ](int x) { return x + x + x; };
    queue<pair<int, int>> que;

    que.emplace(make_pair(0, x));

    while (!que.empty())
    {
        auto& pr = que.front(); que.pop();

        if (pr.second == y)
            return pr.first;
        else if (y < pr.second)
            continue;

        que.emplace(make_pair(pr.first + 1, op1(pr.second)));
        que.emplace(make_pair(pr.first + 1, op2(pr.second)));
        que.emplace(make_pair(pr.first + 1, op3(pr.second)));
    }

    return -1;
}

 

두 번째 풀이에서는 값을 저장하는 set 2개를 활용했고 연산 횟수는 별도로 증가시켜 해결했다.

 

중복을 제거하기 위해 set을 활용했고 set은 front와 back이 존재하지 않기 때문에 2개를 사용해야 했다.

• unordered_set을 사용해도 되고, 이럴 거면 그냥 큐를 쓰는 게 더 나앗을 것 같다.

 

#include <iostream>
#include <set>
#include <utility>

using namespace std;

int solution(int x, int y, int n)
{
    int answer = 0;
    auto op1 = [n](int x) { return x + n; };
    auto op2 = [ ](int x) { return x + x; };
    auto op3 = [ ](int x) { return x + x + x; };
    set<int> st1, st2;

    st1.emplace(x);

    while (!st1.empty() || !st2.empty())
    {
        set<int>& st = (st1.empty()) ? st2 : st1;
        set<int>& stE = (st1.empty()) ? st1 : st2;

        for (int e : st)
        {
            if (e == y)
                return answer;
            else if (y < e)
                continue;

            stE.emplace(op1(e)),
            stE.emplace(op2(e)),
            stE.emplace(op3(e));
        }

        st.clear();
        ++answer;
    }

    return -1;
}

 

여기서부터는 다른 사람의 풀이다.

 

큐를 사용하면서 독특한 방법을 사용했는데, x부터 계산하는 것이 아니라 y부터 나누고 빼면서 계산했다.

 

그러면서 2나 3으로 나누어 떨어지지 않거나 n보다 작은 수들은 스킵하며 진행했다.

 

앞에서부터 하는 것과 실제 실행 시간은 비슷할 것 같다.

 

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int solution(int x, int y, int n)
{
    queue<pair<int, int>> que;

    que.emplace(make_pair(y, 0));

    while (!que.empty())
    {
        int val = que.front().first;
        int count = que.front().second;
        que.pop();

        if (val == x)
            return count;
        else if (val < x)
            continue;

        if (~val & 1)
            que.emplace(make_pair(val / 2, count + 1));
        if (val % 3 == 0)
            que.emplace(make_pair(val / 3, count + 1));
        if (n < val)
            que.emplace(make_pair(val - n, count + 1));
    }

    return -1;
}

 

DP를 이용한 신박한 방법이다.

 

x부터 y까지 for문을 돌아야 하기 때문에 시간은 좀 오래 걸리지만 굉장히 단순하다.

 

또, 특별한 로직 없이 min() 함수를 통해 현재 값을 만들기 위한 연산의 조합들 중 가장 연산 횟수가 적은 조합을 알아서 계산할 수 있다.

 

DP는 알아두면 써먹을 데가 참 많은 것 같다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int solution(int x, int y, int n)
{
    int answer;
    int* dp = new int[1'000'001];

    fill(dp, dp + 1'000'001, 10'000'000);
    dp[x] = 0;

    for (int i = x; i <= y; ++i)
    {
        if (i + n <= y)
            dp[i + n] = min(dp[i + n], dp[i] + 1);
        if (i * 2 <= y)
            dp[i * 2] = min(dp[i * 2], dp[i] + 1);
        if (i * 3 <= y)
            dp[i * 3] = min(dp[i * 3], dp[i] + 1);
    }

    answer = (dp[y] == 10'000'000) ? -1 : dp[y];

    delete[] dp;
    dp = nullptr;

    return answer;
}