G. Shell Game

Editor: 김정현(powergee)

문제 상황 설명

Bessie와 Elsie가 뒤집은 컵 세 개 중 하나에 조약돌을 넣고 한 쌍의 컵의 위치를 바꾸는 것을 여러 번 반복하면서 조약돌의 위치를 맞추는 놀이를 하고 있습니다. 여기서 Bessie는 처음에 조약돌을 어디에 넣었는지를 알려주지 않고, Elsie는 매번 컵의 위치가 바뀔 때마다 조약돌의 위치를 감으로 맞춥니다. Elsie가 조약돌의 위치를 1번 맞출때마다 1점을 얻게 되며, Bessie가 컵 한 쌍의 자리를 바꾸는 행동을 N번 합니다. 입력으로 Bessie가 위치를 바꾼 한 쌍의 컵 번호와 Elsie가 그 이후 찍은 컵의 번호가 총 N 줄 주어집니다. 이때 Elsie가 얻을 수 있는 최대 점수를 산출해야 합니다.

문제 풀이

이 문제 상황에서 Elsie가 최종적으로 받는 점수의 경우의 수가 3가지라는 것은 자명합니다. 왜냐하면 N번의 컵 위치 교환과, N번의 Elsie의 예상이 이미 정해져 있는 시점에서, 처음에 조약돌이 1번에 있느냐, 2번에 있느냐, 3번에 있느냐에 따라 Elsie가 맞춘 예상의 개수가 달라질 것이기 때문입니다.

문제의 풀이를 예제 입력과 함께 생각해보겠습니다. 문제의 예제 입력은 아래와 같습니다.

3
1 2 1
3 2 1
1 3 1

위 예제 입력을 해석하면, Bessie가 컵의 위치를 교환하는 것과 Elsie가 조약돌의 위치를 찍은 것을 각각 3번씩 하였는데, 첫 번째에 Bessie는 1번 컵과 2번 컵을 바꾸고, Elsie는 1번에 조약돌이 있을 것으로 예상하였습니다. 같은 방법으로, 두 번째에 Bessie는 3번과 2번을 바꾸고 Elsie는 1번을 찍었으며, 마지막으로 세 번째에 Bessie가 1번과 3번을 바꾸고 Elsie는 또다시 1번을 찍었습니다.

여기서 조약돌이 처음에 1번, 2번, 3번에 있었을 경우를 나누어 생각할 수 있습니다. 먼저 조약돌이 1번에 있었을 경우 나타나는 놀이의 흐름은 아래 표와 같습니다.

구분	Bessie가 바꾼 컵	1번 컵	2번 컵	3번 컵	Elsie의 예상	누적 점수
놀이 시작 전	-	O	X	X	-	-
1회차	(1, 2)	X	O	X	1	0
2회차	(3, 2)	X	X	O	1	0
3회차	(1, 3)	O	X	X	1	1

위 표에서 알 수 있듯, 이 경우 Elsie는 단 1점 밖에 얻을 수 없습니다. 처음에 조약돌이 2번에 있었을 때와 3번에 있었을 때의 흐름은 아래 두 표와 같습니다.

구분	Bessie가 바꾼 컵	1번 컵	2번 컵	3번 컵	Elsie의 예상	누적 점수
놀이 시작 전	-	X	O	X	-	-
1회차	(1, 2)	O	X	X	1	1
2회차	(3, 2)	O	X	X	1	2
3회차	(1, 3)	X	X	O	1	2

구분	Bessie가 바꾼 컵	1번 컵	2번 컵	3번 컵	Elsie의 예상	누적 점수
놀이 시작 전	-	X	X	O	-	-
1회차	(1, 2)	X	X	O	1	0
2회차	(3, 2)	X	O	X	1	0
3회차	(1, 3)	X	O	X	1	0

위의 3가지 표를 통해 예제 입력의 정답을 알 수 있습니다. 조약돌이 1번, 2번, 3번에 있을 때 각각 1, 2, 0점을 획득할 수 있으므로 정답은 최대 점수인 2점이 됩니다.

지금까지 한 과정이 이 문제의 풀이가 됩니다. 즉 우리가 구현하는 소스코드에는 이 과정을 시뮬레이션하는 기능이 포함되기만 하면 됩니다. 조약돌의 처음 위치를 1, 2, 3 중 하나로 정했을 때 입력으로 들어온 대로 컵의 내용물을 교체하고, 그 후 예상한 위치에 조약돌이 있다면 1점을 추가하는 식으로 반복문이나 재귀호출문을 이용하여 구현하면 됩니다. 그리고 마지막의 출력은 그 3가지 경우의 수 중 가장 큰 점수를 출력하면 정답입니다.

정답 소스 (C++)

#include <iostream>
#include <algorithm>

int n;
int guessed[100];
std::pair<int, int> swaps[100];

int GetPoint(int pePos)
{
    int points = 0;
    for (int i = 0; i < n; ++i)
    {
        if (swaps[i].first == pePos)
            pePos = swaps[i].second;
        else if (swaps[i].second == pePos)
            pePos = swaps[i].first;

        if (pePos == guessed[i])
            ++points;
    }

    return points;
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; ++i)
        scanf("%d %d %d", &swaps[i].first, &swaps[i].second, &guessed[i]);
    
    printf("%d", std::max(GetPoint(1), std::max(GetPoint(2), GetPoint(3))));

    return 0;
}