숨바꼭질 5

Problem link: https://www.acmicpc.net/problem/17071

크게 어렵지 않게 풀었는데, 풀이까지 이르게 된 사고의 흐름이 나름 기억해둘만해서 조금은 자세히 기록한다.

아래는 풀이와는 무관한 사고의 흐름이다.

• 처음에 문제를 보고 1차원 DP로 풀 수 있겠거니 생각했다(CACHE[i]: i에 도착하는 데 걸리는 최소 시간과 같이).

• 그런데, 문제를 자세히보니 수빈이는 앞/뒤/점프 이동 모두가 가능해서 최소 시간은 의미가 없을 뿐더러 sub-problem 정의도 어려운 것을 알 수 있었다(CACHE[i]가 CACHE[i-1]을 sub-problem으로 갖는데, CACHE[i-1]은 다시 CACHE[i]를 sub-problem으로 갖음).

• 따라서, 2차원 DP를 활용해서 풀어보고자 했는데 이 경우에는 문제의 크기가 제한 시간을 만족시키기에는 너무 큰 것을 알 수 있었다(CACHE[i][s]: s초에 수빈이가 i에 있는 것이 가능한지의 여부).

• 자연스럽게 BFS로 방향을 틀어서 생각해보았고, 조금의 응용을 통해 문제를 풀 수 있었다.

문제를 푸는 아이디어는 아래와 같다.

수빈이가 n초 후에 i에 위치한다면, 자연스럽게 i+2, i+4, ..., i+짝수 초 후에도 i에 위치할 수 있다.

따라서, 아래와 같이 visit을 관리하여 BFS를 수행해준다.

• visit[i][x]: 짝수 초(x==0) 또는 홀수 초(x==1) 후에 i에 도달할 때 가장 빠른 도달 시간

BFS를 진행하므로 가장 빠른 도달시간을 구하는데에는 큰 어려움이 없다.

x초 후에 둘이 i에서 만난다는 사실은 x - visit[i][x % 2] mod 2 == 0 으로 표현해 줄 수 있다(단, x >= visit[i][x % 2]).

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

using namespace std;

const int kMaxN = 500000;

int SUBIN;
int BROTHER;

int VISIT[kMaxN + 1][2];

void Bfs()
{
  queue<pair<int, int> > q;

  VISIT[SUBIN][0] = 0;
  q.emplace(SUBIN, 0);

  while (!q.empty())
  {
    int here = q.front().first;
    int odd = q.front().second;
    q.pop();

    if (0 <= here - 1 && VISIT[here - 1][1 - odd] == -1)
    {
      VISIT[here - 1][1 - odd] = VISIT[here][odd] + 1;
      q.emplace(here - 1, 1 - odd);
    }

    if (here + 1 <= kMaxN && VISIT[here + 1][1 - odd] == -1)
    {
      VISIT[here + 1][1 - odd] = VISIT[here][odd] + 1;
      q.emplace(here + 1, 1 - odd);
    }

    if (here * 2 <= kMaxN && VISIT[here * 2][1 - odd] == -1)
    {
      VISIT[here * 2][1 - odd] = VISIT[here][odd] + 1;
      q.emplace(here * 2, 1 - odd);
    }
  }
}

int Solve()
{
  Bfs();

  for (int sec = 0;; ++sec)
  {
    BROTHER += sec;
    if (BROTHER > kMaxN)
    {
      return -1;
    }
    else if (VISIT[BROTHER][sec % 2] != -1 && VISIT[BROTHER][sec % 2] <= sec &&
             (sec - VISIT[BROTHER][sec % 2]) % 2 == 0)
    {
      return sec;
    }
  }
}

int main(void)
{
  // Initialize
  for (int i = 0; i < kMaxN + 1; ++i)
  {
    VISIT[i][0] = -1;
    VISIT[i][1] = -1;
  }

  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> SUBIN >> BROTHER;

  // Solve
  cout << Solve() << '\n';

  return 0;
}