17071 숨바꼭질5

문제 링크

• 나의 풀이

시간의 홀짝 여부에 따라 -1, +1이동으로 재방문의 가능함을 활용하여 DP스럽게 풀 수 있었다.

#include <iostream>
#include <queue>
#include <ctime>

using namespace std;

int N, K;
int m[500001];

int solve()
{
    int ret = 0;
    queue<int> q;

    q.push(N);
    m[N] = 2;

    while (true)
    {
        if (K > 500000)
            return -1;

        int sz = q.size();

        int parity = ((ret + 1) % 2) ? 1 : 2;
        int cur_parity = ((ret % 2) ? 1 : 2);
        while (sz--)
        {
            int f = q.front();
            q.pop();

            if (f == K || m[K] & cur_parity)
                return ret;

            if (f + 1 <= 500000 && !(m[f + 1] & parity))
            {
                q.push(f + 1);
                m[f + 1] += parity;
            }
            if (f * 2 <= 500000 && !(m[f * 2] & parity))
            {
                q.push(f * 2);
                m[f * 2] += parity;
            }
            if (f - 1 >= 0 && !(m[f - 1] & parity))
            {
                q.push(f - 1);
                m[f - 1] += parity;
            }
        }

        ret += 1;
        K += ret;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;

    clock_t st, ed;

    st = clock();
    cout << solve() << "\n";
    ed = clock();

    cout << ed - st << "\n";
}

• 다름사람 풀이

나는 홀짝을 parity라는 변수를 만들어 번거롭게 사용하였지만 다차원 배열을 이용해 캐싱 하면 더욱 편리하다.