[백준 12993번] 이동3 (C++)

문제링크 : https://www.acmicpc.net/problem/12993

12993번: 이동3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

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

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

    bool flag = 0;
    if(x==0 && y==0) flag = 1; //예외처리

    int mutiple = 1;
    int i; //곱해진 횟수
    for(i=1; i<20; i++)
    {
        mutiple *=3;
        if(mutiple > max(x,y))
        {
            mutiple/=3;
            break;
        }
    }

    for(int j=0; j<=i; j++)
    {
        if(x>y) //큰 값부터 하나씩 빼줌
        {
            x-= mutiple;
            mutiple/=3;
        }
        else
        {
            y-= mutiple;
            mutiple/=3;
        }
    }

    if(x==0 && y==0) flag = 1;
    cout << (flag==1 ? 1 : 0);

    return 0;
}

3씩 계속 곱해주면서 해당 값이 max(x, y)보다 커질 때 종료한다.

이때 곱해준 해당 값에 3을 나눠주는데 이는 바로 직전 값을 필요로 하기 때문이다.

 

다음으로 곱해진 횟수라고 할 수 있는 i만큼 큰 값부터 하나씩 빼주기 시작한다.

값을 빼주고 난 뒤에는 단계 번호를 낮추기 위해 3씩 계속 곱해줬던 값에 이번엔 3을 나눠줘야 한다.