백준 17071 숨바꼭질 5

김형훈

안녕하세요.
김형훈입니다.

Yongin

백준 17071 숨바꼭질 5

2022년 12월 4일

cpp, 탐색

문제

문제 링크

풀이

수빈이는 앞 뒤로 움질일 수 있다.
즉, 어떤 위치 x에 도달한 시간이 t초라면, 1초 후 x+1에 갔다가 다시 x에 돌아올 수 있다.
즉, 어떠한 위치 x에 대하여 t초에 도달 가능하다면, t+2,t+4,t+6,…초에도 도달 가능하다.
만약 동생이 x에 q초에 도달하였다고 한다면, 수빈이가 해당 위치에 도달한 시간이 q,q-2,q-4,…중 하나이면 수빈이가 동생을 찾는데 성공했다고 할 수 있다.
어떤 위치 x에 대해 수빈이가 가장 빠르게 도달 가능한 시간을 기록한다.
이때, 도달한 시간은 홀수와 짝수 시간대로 나누어서 계산한다. 이후, 동생이 해당 위치에 도착했을때, 도착한 시간이 수빈이가 도착한 시간보다 같거나 높으면 수빈이와 동생이 바로 만났거나, 수빈이가 앞뒤로 움직이다가 만났다는걸 알 수 있다.

코드

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

int n,k;
int dist[500'002][2];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    queue<pair<int,int>> q;
    dist[n][0] = 1;
    q.push({n,0});
    while(!q.empty()){
        auto [x,d] = q.front(); q.pop();
        for(int nx:{2*x,x-1,x+1}){
            if(nx<0||nx>500000) continue;
            if(dist[nx][(d+1)%2]) continue;
            dist[nx][(d+1)%2] = d + 1;
            q.push({nx,d+1});
        }
    }
    int i = 0;
    while(k <= 500000){
        if(dist[k][i%2]-1 <= i){
            cout << i;
            return 0;
        }
        k += ++i;
    }
    cout << -1;
}

결과

시간초과와 메모리초과 지옥에 빠져 정말 괴롭게 풀었다.

boj 카테고리의 다른 글

(모든 카테고리)

백준 20304 비밀번호 제작

2022년 12월 17일

cpp, 완전 탐색

백준 1799 비숍

2022년 12월 17일

Yongin

백준 17071 숨바꼭질 5

백준 17071 숨바꼭질 5

문제

문제

풀이

풀이

코드

코드

결과

결과

백준 20304 비밀번호 제작

백준 1799 비숍

백준 9663 N-Queen

백준 16235 나무 제테크

백준 16920 확장 게임

이전

1/1

다음

백준 20304 비밀번호 제작

백준 1799 비숍

백준 9663 N-Queen

백준 16235 나무 제테크

백준 16920 확장 게임

이전

1/1

다음

백준 20304 비밀번호 제작

백준 1799 비숍

백준 9663 N-Queen

백준 16235 나무 제테크

백준 16920 확장 게임

이전

1/1

다음

문제

풀이

코드

결과

안녕하세요.
김형훈입니다.