[BOJ] 20093 Coins

문제 설명

$8 \times 8$ 크기의 체스보드가 있습니다. $A$와 $B$가 이 위에서 게임을 합니다. 각 체스보드에는 동전이 하나씩 올려져 있고, 처음 상태는 무작위입니다. $A$는 동전을 최대 한 개 뒤집어서, $0$ 이상 $63$ 이하의 정수 하나를 체스보드만 보고 $B$가 알 수 있게끔 해야 합니다. $A$와 $B$의 전략을 직접 구현해 제출하는 투 스텝 문제입니다.

문제 관찰

서브태스크 1

동전을 하나 뒤집을 수 있다는 건, 원하는 위치의 동전을 위 또는 아래로 정확히 맞출 수 있다는 것과 동치입니다. 따라서 0번 위치의 동전을 잘 뒤집어 주면 됩니다.

서브태스크 4

서브태스크 1과 비슷한 느낌으로 접근합시다. $A$가 $B$에게 전달해야 하는 정보는 정확히 6비트어치입니다. 따라서 6개의 동전만 잘 설정해주면 알려줄 수 있습니다. 이렇게 6비트어치 정보를 전달한다라는 생각이 이 문제의 키포인트가 됩니다.

서브태스크 5

동전을 딱 하나 뒤집었을 때 1비트를 전달하는 것은 서브태스크 1에서 보았습니다. 그런데 이 방법으로는 1비트를 초과하는 정보를 전달할 수 없음이 너무 명확합니다. 그리고, 나머지 63개의 동전을 사용하지 않는 것 또한 너무 맘에 들지 않습니다. 그러므로 비트를 전달하는 다른 방식을 생각해 보아야 합니다.

$A$ 입장에서 잠시 생각해봅시다. $A$가 취할 수 있는 액션은 정확히 64가지입니다. $A$가 전달해야 하는 수도 0부터 63 중 하나이므로, 처음 상태와 무관하게 하나의 동전 뒤집기가 하나의 수에 대응되어야 합니다. 따라서 어떤 비트를 결정할 때, 그 비트가 1이게 만드는 칸 32개와 0이게 만드는 칸 32개가 존재해야 합니다. 여기까지만 찾으면 그 다음부터는 매우 쉽습니다.

비트 딱 하나만 가지고 생각해봅시다. 임의로 체스보드를 2분의 1로 쪼개면, 위쪽 절반에서 켜져 있는 동전의 기우성을 가지고 생각할 수 있습니다(1비트 어치 정보라면 다른 방법으로 해도 무방합니다). 만약 뒤집어야 한다면 위쪽 아무데나 뒤집으면 되고, 아니면 아래쪽 아무데나 뒤집으면 됩니다. 그러면 홀수/짝수라는 1비트어치 정보를 전달할 수 있습니다.

다시 $A$ 입장에서 잠시 생각해봅시다. $A$가 취할 수 있는 액션은 정확히 32가지입니다. $A$가 전달해야 하는 수도 0부터 31 중 하나이므로(비트 하나는 알고 있습니다), 처음 상태와 무관하게 하나의 동전 뒤집기가 하나의 수에 대응되어야 합니다. 따라서 어떤 비트를 결정할 때, 그 비트가 1이게 만드는 칸 16개와 0이게 만드는 칸 16개가 존재해야 합니다. 여기까지만 찾으면 그 다음부터는 매우 쉽습니다.

두 번째 비트는 어떻게 전달해야 할까요? 위에서 어떤 방법을 사용했건 간에, 그대로 반을 한번 더 쪼개면 됩니다. 이렇게 쪼개고 32개의 동전을 비슷하게 절반 찢어서 봅시다. 만약 동전을 뒤집어야 하면 어떤 곳이던 간에 뒤집으면 되고, 아니면 동전을 뒤집지 않으면 됩니다. 동전을 뒤집지 않는다는 선택지는 나머지 절반 아무데나 뒤집어서 해결할 수 있습니다.

(대충 뇌절 시작)

다시 다시 $A$ 입장에서 잠시 생각해봅시다. $A$가 취할 수 있는 액션은 정확히 16가지입니다. $A$가 전달해야 하는 수도 0부터 15 중 하나이므로(비트 두 개는 알고 있습니다), 처음 상태와 무관하게 하나의 동전 뒤집기가 하나의 수에 대응되어야 합니다. 따라서 어떤 비트를 결정할 때, 그 비트가 1이게 만드는 칸 8개와 0이게 만드는 칸 8개가 존재해야 합니다. 여기까지만 찾으면 그 다음부터는 매우 쉽습니다.

세 번째 비트는 어떻게 전달해야 할까요? 위에서 어떤 방법을 사용했건 간에, 그대로 반을 한번 더 쪼개면 됩니다. 이렇게 쪼개고 16개의 동전을 비슷하게 절반 찢어서 봅시다. 만약 동전을 뒤집어야 하면 어떤 곳이던 간에 뒤집으면 되고, 아니면 동전을 뒤집지 않으면 됩니다. 동전을 뒤집지 않는다는 선택지는 나머지 절반 아무데나 뒤집어서 해결할 수 있습니다.

다시 다시 다시 $A$ 입장에서 잠시 생각해봅시다. $A$가 취할 수 있는 액션은 정확히 8가지입니다. $A$가 전달해야 하는 수도 0부터 7 중 하나이므로(비트 세 개는 알고 있습니다), 처음 상태와 무관하게 하나의 동전 뒤집기가 하나의 수에 대응되어야 합니다. 따라서 어떤 비트를 결정할 때, 그 비트가 1이게 만드는 칸 4개와 0이게 만드는 칸 4개가 존재해야 합니다. 여기까지만 찾으면 그 다음부터는 매우 쉽습니다.

네 번째 비트는 어떻게 전달해야 할까요? 위에서 어떤 방법을 사용했건 간에, 그대로 반을 한번 더 쪼개면 됩니다. 이렇게 쪼개고 8개의 동전을 비슷하게 절반 찢어서 봅시다. 만약 동전을 뒤집어야 하면 어떤 곳이던 간에 뒤집으면 되고, 아니면 동전을 뒤집지 않으면 됩니다. 동전을 뒤집지 않는다는 선택지는 나머지 절반 아무데나 뒤집어서 해결할 수 있습니다.

다시 다시 다시 다시 $A$ 입장에서 잠시 생각해봅시다. $A$가 취할 수 있는 액션은 정확히 4가지입니다. $A$가 전달해야 하는 수도 0부터 3 중 하나이므로(비트 네 개는 알고 있습니다), 처음 상태와 무관하게 하나의 동전 뒤집기가 하나의 수에 대응되어야 합니다. 따라서 어떤 비트를 결정할 때, 그 비트가 1이게 만드는 칸 2개와 0이게 만드는 칸 2개가 존재해야 합니다. 여기까지만 찾으면 그 다음부터는 매우 쉽습니다.

다섯 번째 비트는 어떻게 전달해야 할까요? 위에서 어떤 방법을 사용했건 간에, 그대로 반을 한번 더 쪼개면 됩니다. 이렇게 쪼개고 4개의 동전을 비슷하게 절반 찢어서 봅시다. 만약 동전을 뒤집어야 하면 어떤 곳이던 간에 뒤집으면 되고, 아니면 동전을 뒤집지 않으면 됩니다. 동전을 뒤집지 않는다는 선택지는 나머지 절반 아무데나 뒤집어서 해결할 수 있습니다.

다시 다시 다시 다시 다시 $A$ 입장에서 잠시 생각해봅시다. $A$가 취할 수 있는 액션은 정확히 2가지입니다. $A$가 전달해야 하는 수도 0부터 1 중 하나이므로(비트 다섯 개는 알고 있습니다), 처음 상태와 무관하게 하나의 동전 뒤집기가 하나의 수에 대응되어야 합니다. 따라서 어떤 비트를 결정할 때, 그 비트가 1이게 만드는 칸 1개와 0이게 만드는 칸 1개가 존재해야 합니다. 여기까지만 찾으면 그 다음부터는 매우 쉽습니다.

여섯 번째 비트는 어떻게 전달해야 할까요? 위에서 어떤 방법을 사용했건 간에, 그대로 반을 한번 더 쪼개면 됩니다. 이렇게 쪼개고 2개의 동전을 비슷하게 절반 찢어서 봅시다. 만약 동전을 뒤집어야 하면 어떤 곳이던 간에 뒤집으면 되고, 아니면 동전을 뒤집지 않으면 됩니다. 동전을 뒤집지 않는다는 선택지는 나머지 절반 아무데나 뒤집어서 해결할 수 있습니다.

(대충 뇌절 끝)

따라서 총 6비트어치 정보를 전달할 수 있으므로 문제를 해결할 수 있습니다.

문제 풀이

하지만 위에서 서술한 풀이로 그대로 풀어야 했다면, 문제는 아무리 못해도 플래티넘 5 이상을 받아야 할 것입니다. 그러나 체스보드의 관점에서 벗어나서, 그냥 수 0부터 63까지를 전달한다고 생각하면 저 기우성 그룹을 다른 방식으로 나눌 수 있습니다(이 경우 구체적으로 나누는 방법을 construct할 필요가 없이, 그냥 적당히 반으로 계속 쪼갠다는 아이디어만 들고 오면 됩니다). 저걸 위아래가 아니라 홀수번째 줄 / 짝수번째 줄로 나눈다고 생각합시다. 이러면 실제로 홀수와 짝수가 나뉘게 됩니다. 이건 체스보드에 써 있는 6비트 중 마지막 비트를 기준으로 그룹을 나눈 것과 같습니다.

이런 느낌으로 마지막에서 두 번째 비트를, 세 번째 비트를, 네 번째 비트를... 과 같이 나눠봅시다. 그러면 결국 체스보드에 써져 있는 숫자를 이진수로 나타냈을 때 비트별로 그룹을 나눈 것과 다르지 않고, 그래서 각 비트별로 켜져 있는 동전들의 기우성만 따져주면 됩니다. 이건 Naive하게 구현해도 되고, XOR을 이용해서 우아하게 구현할 수도 있습니다. 켜져 있는 모든 동전들을 XOR하면 모든 그룹의 기우성이 바로 나오므로, 그 기우성을 원하는 결과 $C$로 맞춰주게끔 동전 하나를 뒤집어주면 됩니다. 기우성을 나타내는 수가 $X$라고 할 때 $X \oplus C$를 뒤집으면 $X$를 $C$로 바꿀 수 있습니다. XOR 자체가 문제의 핵심이 아니고, 관찰을 편하게 구현하는 하나의 수단이라고 생각하시면 될 것 같습니다.

여담

실제로 문제를 풀 때는 이렇게까지 깊게 고민하면서 풀지는 않았고, 서브태스크 4를 보고 6비트만 전달하면 되겠구나 생각한 뒤에 그냥 직관적으로 체스보드를 반씩 갈라가면서 비트 하나씩 뽑아내면 되지 않을까 하면서 풀었습니다. 그러다 보니 체스보드를 가르는 것 보다 그냥 비트 자리수별로 가르는 게 더 효율적일 것이라는 생각을 했고, 그냥 적당히 XOR로 구현했습니다. 푸는 데 풀이부터 구현까지 약 10분정도 걸렸습니다.

아직도 골드급 문제라는 생각에는 변함이 없지만, 직관적인 풀이를 다시 엄밀하게 정리해보니 기존에 주었던 Gold 4는 너무 낮은 게 아닌가 싶습니다. 고민하고 이렇게 글 작성할 기회를 주신 jh05013님께 감사 인사를 드립니다.