백준 12994 - 이동 3-2

https://www.acmicpc.net/problem/12994

 

문제에 음수 방향으로도 갈 수 있다는 조건이 있어 어떤 값의 조합으로 되어있는지 찾기 어렵다.

 

다만 더하거나 빼는 수는 $3^{k}$으로만 이루어졌다는 부분에 주목할 수 있는데, 이는 x와 y에 배분하는 경우를 2진법으로 나타낼 수 있다는 것이다.

 

x와 y를 빼지 않고 더하는 경우만 있다고 해보자.

 

예시를 들어 $sum = x + y$라고 할 때 $sum = 11111_{3}$라고 하자.

 

그러면 $x = 11100_{3}, y = 00011_{3}$으로 나타낼 수 있다.

 

x와 y의 자릿수에는 1이 중복으로 나타나면 안 되는데, 어떤 자릿수에 중복으로 1이 나타나면 같은 단계를 반복하지 않는다는 문제 조건에 모순이 되기 때문이다.

 

따라서 두 수를 2진법으로 표현했을 때 중복으로 1인 자리가 없으며 중간에 비어있는 자리가 없는지를 확인하면 더 쉬운 조건을 가진 이동 3-1을 풀 수 있다.

 

그러면 음수로도 갈 수 있는 이 문제는 어떻게 해야 할까?

 

아까 전에는 자릿수가 0 또는 1인 경우에 대해서만 논했다. 그렇다면 양의 방향이 아니라 음의 방향으로 이동한 $-3^{k}$를 더한 경우에 대해 -1로 하여 각 진법의 숫자를 삼진법 $\{-1, 0, 1\}$로 표현하는 것을 고려할 수 있다.

 

하지만 어떤 것이 음수인지 어떻게 알 수 있을까? (0, 2)의 경우를 살펴보자.

 

2 = 3 - 1인 것은 쉽게 생각할 수 있으며 리틀 엔디언으로 나타내면 $(1)(-1)_{3}$이 된다.

 

여기서 다음 공식을 생각해볼 수 있다.

 

$2 \times 3^{k} = 3^{k + 1} - 3^{k}$

 

이 식의 의미는 어떤 자릿수에서 3으로 나눈 나머지가 2라면 그것은 다음 단계의 자릿수에서 현 단계의 자릿수를 빼서 2라는 뜻이다.

 

이를 확장하여 수를 $\{-1, 0, 1\}$ 집합의 3진법으로 나타내서 3으로 나눌 때 나머지가 2라면 뺀 것이므로 -1로 바꿔주고 다음 자릿수에 1을 올려주는 방식으로 어떤 수가 더해지고 빼졌는지 복구할 수 있다.

 

이렇게 x와 y를 3진법으로 표현하여 중간에 중복과 비는 자릿수가 없이 수를 완성할 수 있는지 확인하면 문제를 해결할 수 있다.