BOJ 12994 : 이동3-2

• 문제 링크 : boj.kr/12994
• 난이도 : G5
• 태그 : 정수론

12994번: 이동3-2

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int x, y;
    cin >> x >> y;

    int step = 1;
    while(x != 0 || y != 0) {
        bool flag = false;
        if(x != 0 && (x + step) % (step * 3) == 0) {
            x += step;
            flag = true;
        }
        else if(x != 0 && (x - step) % (step * 3) == 0) {
            x -= step;
            flag = true;
        }
        if(flag) {
            step *= 3;
            continue;
        }
        if(y != 0 && (y + step) % (step * 3) == 0) {
            y += step;
            flag = true;
        }
        else if(y != 0 && (y - step) % (step * 3) == 0) {
            y -= step;
            flag = true;
        }
        if(flag) {
            step *= 3;
            continue;
        }
        if(!flag) {
            break;
        }
    }

    if(x == 0 && y == 0) cout << 1;
    else cout << 0;

    return 0;
}

---

풀이

현재의 위치에서 0단계부터 반대로 추적해보자.

$3^1, 3^2, 3^3, \cdots$는 3의 배수이므로 현재의 위치에서 0단계의 움직임의 반대로 이동한 좌표는 3의 배수여야 한다.

마찬가지로 현재의 위치에서 k-1단계까지의 움직임을 반대로 이동한 좌표는 $3^k$의 배수여야 한다.

따라서 k-1단계에서 이동한 방향은 반대로 이동했을 때 모든 좌표가 $3^k$가 되는 방향으로 이동했다고 할 수 있다.

이 과정을 모든 좌표가 0이 될 때까지 반복하면 된다.

단 모든 단계에서 반드시 움직여야 하는데, 어느 방향으로 이동하더라도 조건을 충족하지 못한다면 이는 불가능한 이동으로 판단할 수 있다.