BOJ 1399 - 보물의 위치

BOJ - 보물의 위치

딱 보면 문제가 뭔가 싸이클을 찾아서 $k\le 10^9$ 라는 조건을 빠르게 처리해주어야 할 것 같다.

문제에서 시키는대로 구현을 해보자.

골드 넘버 싸이클

일단 골드 넘버라는게 계속해서 커지므로 이걸 처리해주어야 한다.

골드 넘버가 한자리 수가 될 때 까지 $dig$를 적용시켜주는 것이 어떤 성질을 지니는지를 살펴봐야한다.

사실 이건 그냥 전진해야 할 값에 대해서 주기성을 가진다고 가정하고 푸는게 가장 편하다.

팁

팁은 $dig(G)$ 를 $9$ 에 대한 나머지를 구하는 것으로 구할 수 있다는 것이다.

단, $dig(G)\ne0$ 이기 때문에 $0$이 나온다면 $9$를 써주도록 하자.

이건 귀납적으로 증명할 수 있다.

일단 $G<10$ 이라면 자명하고 $10\le G<91$ 라고 해보자. 이 수들에 9를 더하면 항상 자리수가 같다는 것은 쉽게 파악된다.

즉 백의자리가 바뀌지 않을 때 십의 자리끼리의 덧셈은 9를 더하면 항상 일정하단 것을 보였다.

이제 더 큰 자리수들이 바뀐다고 하자. 그럼 더 큰 자리수는 자리수가 추가되거나 아니면 값이 1 증가되거나 자리가 1 증가하고 일의 자리는 1 감소한다. 따라서 값의 변화가 없다.

따라서 수가 계속해서 커져도 값이 변하지 않으므로 9로 나누면 $dig$ 를 얻게된다.

구현

$dig(G) \to (MG)$ 에 대한 주기를 구하고 $K$ 를 나머지 연산 때려서 줄여서 풀면 된다.

필자는 풀기 쉽게 $dir,~G$ 를 페어로 잡고 메모이제이션을 했다.

const int dy[] = {1, 0, -1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};
void solve() {
   int k, m;
   cin >> k >> m;
   map<pi, array<int, 3>> dp;
   pi pos;
   int dir = 0, gold = 1;

   dp[mp(0, 1)] = {0, 0, 0};

   vi vis(10);
   vis[1] = 1;

   for (int i = 1; i <= k; i++) {
      int step = gold % 9;
      if(step == 0) step = 9;
      if (vis[step]) gold = step;
      vis[step] = 1;
      pos.fi = pos.fi + dy[dir] * step;
      pos.se = pos.se + dx[dir] * step;
      dir = md(4, dir + 1);
      gold = gold * m;

      pi key = mp(dir, gold);
      if (hass(dp, key)) {
         int DY = pos.fi - dp[key][0];
         int DX = pos.se - dp[key][1];
         int DT = i - dp[key][2];
         int Q = (k - i) / DT;
         pos.fi += DY * Q;
         pos.se += DX * Q;
         k -= Q * DT;
         dp[key] = {pos.fi, pos.se, i};

      } else {
         dp[key] = {pos.fi, pos.se, i};
      }
   }

   cout << pos.se << ' ' << pos.fi << endl;
}