[백준]숨바꼭질 5(17071)

문제 링크 : [백준]숨바꼭질 5(17071)

17071번: 숨바꼭질 5

문제 설명

수빈이와 동생이 각각 N, K 좌표에 있습니다.

수빈이는 1초에 원래 좌표에서 +1, -1, *2의 좌표로 이동할 수 있습니다.

동생은 원래 좌표 + 시간(1초가 지났으면 1, 2초가 지났으면 2)만큼 움직입니다.

둘이 가장 빠르게 만날 수 있는 시간을 구하세요.(수빈이는 0보다 작거나 500,000보다 큰 좌표로는 이동할 수 없습니다.)

입력

N(수빈이의 위치, 1 <= N <= 500,000)

K(동생의 위치, 1 <= K <= 500,000)

5 17

 

출력

2

 

카테고리

#BFS

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. BFS를 이용하여 구하면 될 것 같지만, 둘이 동시간대에 동일한 위치에 있어야 하는 조건이 있습니다.
2. 그래서 visited 배열을 위치와 시간 2차원 배열로 구성되어야 합니다.
3. 그러나 그렇게 되면 O(N2)의 시간복잡도가 발생하게 되어 시간초과가 발생합니다.
4. 다르게 생각해보면, 수빈이나 특정 위치에 도착했고, 그 이후에 동생이 도착할 위치라면 수빈이는 그 위치에서 +1, -1을 반복하면서 동생을 기다릴 수 있습니다.
5. 하지만 둘이 엇갈릴 수도 있습니다. 
   1. 예시)1초 후에 수빈이는 3, 동생이 1이었다면, 2초 후에는 수빈이는 2, 동생이 3으로 오게 되어 둘이 엇갈림
   2. 예시)0초 후에 수빈이는 3, 동생이 0이었다면,
      1. 1초 후에 수빈이는 2, 동생은 1
      2. 2초 후에는 수빈이는 다시 3, 동생도 3으로 이동하여 만날 수 있습니다.
6. 두 예시의 차이는 수빈이가 도착한 곳에 동생이 도착한 시간과 수빈이가 도착한 시간의 차이입니다.
7. 두 사람이 도착한 시간의 차이가 짝수라면 둘은 만날 수 있습니다.(+1 -1의 반복으로 제로썸)
8. 하지만 차이가 홀수라면 둘은 엇갈리게 됩니다.
9. BFS를 돌리면서 동생이 도착할 위치에 수빈이가 먼저 도착했다면, 그 차이가 짝수인지 홀수인지를 파악하면 됩니다.

시간복잡도

O(N)

코드

#include<cstdio>
#include<queue>
#define M 500001
using namespace std;
int a,b,v[M][2],s,t,p;
queue<int>q;
void x(int p,int s){if(p>-1&&p<M&&!v[p][s&1])v[p][s&1]=1,q.push(p);}
int main(){
    scanf("%d%d",&a,&b);
    q.push(a);
    v[a][0]=1;
    while(1){
        s=q.size();
        t=b+p*(p+1)/2;
        if(t>=M)break;
        while(s--){
            int c=q.front();q.pop();
            x(c-1,p+1);
            x(c+1,p+1);
            x(c*2,p+1);
        }
        if(v[t][p&1]){
            printf("%d",p);
            return 0;
        }
        p++;
    }
    printf("-1\n");
}