백준 12993번 : 이동3

• Solved.ac 기준 실버 2
• 사용언어 C++

문제 해석 및 풀이

설명:

• 각 단계 k에서 동혁이는 3^k 만큼 오른쪽(x 증가) 또는 위(y 증가)로 이동할 수 있음
• 목표는 (x, y)로 이동 가능한지를 판단
• 주어진 (x, y)에서 시작하여 3의 거듭제곱 단위로 역추적하여 (0, 0)으로 갈 수 있는지 확인
• k를 0부터 시작하여 점진적으로 증가

#include <iostream>
using namespace std;

int canGo(int x, int y, int k) {
	int powThree = 1;

	for (int i = 0; i < k; i++) {
		powThree *= 3;
	}

	if (x == 0 && y == 0) {
		return 1;
	}

	if (x < 0 || y < 0) {
		return 0;
	}

	if (x >= powThree && canGo(x - powThree, y, k + 1)) {
		return 1;
	}

	if (y >= powThree && canGo(x, y - powThree, k + 1)) {
		return 1;
	}

	return 0;
}

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

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

	cout << canGo(x, y, 0);

	return 0;
}