숨바꼭질 5

수빈이가 이동한 위치에 동생이 나중에 오게 된다면, -1, +1을 반복하면서 기다릴 수 있는데

시간 차이가 짝수여야 가능하다.

이 부분만 잘 처리하면 간단한 문제가 된다.

visit[i][j]를 i는 시간%2, j는 위치로 해서 체크하면 된다.

그렇게 bfs로 visit 배열을 채워나가면 되는 간단한 문제이다.

#include<stdio.h>
#include<queue>
using namespace std;
int N,K;
queue<pair<int,int>>pos;
int visit[2][500004];
int mov(int p,int type)
{
    if(type==0) return p-1;
    else if(type==1) return p+1;
    else return p*2;
}
int bfs()
{
    pos.push(make_pair(N,0));
    visit[0][N]=1;
    while(!pos.empty())
    {
        pair<int,int> t = pos.front();
        pos.pop();
        int prey = K+t.second*(t.second+1)/2;
        if(prey>500000) break;
        if(visit[t.second%2][prey]==1) return t.second;
        for(int i=0;i<3;i++)
        {
            int next = mov(t.first,i);
            if(next<0 || next>500000) continue;
            if(visit[(t.second+1)%2][next]==1) continue;
            visit[(t.second+1)%2][next]=1;
            pos.push(make_pair(next,t.second+1));
        }
    }
    return -1;
}
int main()
{
    scanf("%d %d",&N,&K);
    int ans = bfs();
    printf("%d",ans);
}

전체 코드이다.