[Python] 10435번 만칼라

 

 

 

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

---

 

25/06/14

 

 

개인적으로 현재 난이도보다 한단계 높은 플레티넘 5정도의 난이도로 느껴진 문제였다.

 

이전에 북마크에 담아두고 고민하다가 못풀었던 문제인데, 다른 블로그 글을 확인해서 힌트를 얻고 해결했다.

 

게임 이론과 해 구성하기가 담겨있는 좋은 문제인 것 같다. 

---

 

문제 접근 방식:

 

 

문제를 해결하기 위해서는 2가지 핵심 아이디어를 알아야 한다.

 

1. 구슬이 $N$개일 때 이기는 상태에서 어떤 "액션"을 취하면 구슬이 $N-1$개일 때 이기는 상태로 바뀐다.

 

2. "액션"을 취하면 $k$번째에 있던 $k$개의 돌들은 모두 없어지고, $1$번째부터 $k-1$번째의 돌 개수는 한 개씩 증가한다.

 

어떤 "액션"을 취한 뒤에도 턴을 이어나가려면, 내가 마지막으로 놓은 돌의 위치가 Roumba이여야하고, 그렇다는 말은 내가 액션을 취할 때마다 구슬의 총 개수는 $1$개씩 줄어든다는 말과 같다.

 

따라서 1번 아이디어에 대한 내용은 당연한 이야기가 된다.

 

2번 아이디어는 게임 룰과 직접적으로 연관이 되어있으므로 당연한 이야기이다.

 

1번 아이디어를 통해 정당성을 만들고 2번 아이디어를 통해 직접적인 해 구성을 하는 방식으로 문제가 해결된다.

 

먼저, 문제에서 나와있다시피 구슬이 $N$개 일때의 이기는 상태는 "유일하다". 물론 이를 증명하지 않고 그냥 풀어도 풀리지만, 실제로 증명을 해보자.

 

증명은 수학적 귀납법을 이용한다. 일단 $N = 1$일 때의 이기는 상태는 $1$번 위치에 돌이 $1$개 있는 상황밖에 없다.

 

이후 구슬이 $N = k$일 때의 이기는 상태가 유일하다고 가정하자. 우리가 보여줄 것은 $N = k+1$일 때 이기는 상태가 유일함을 보여주는 것이다.

 

결론을 부정해서, $N = k+1$일 때 이기는 상태가 유일하지 않다고 해보자. 즉, $N = k$일 때의 이기는 상태가 유일한데 $N = k+1$일 때 이기는 상태가 유일하지 않다고 해보자.

 

편의 상 $N = k+1$일 때 이기는 상태를 각각 $W_1, W_2$라고 하자. 그리고 $N = k$일 때 이기는 상태를 $V$라고 하자.

 

$W_1 \to V$일 때 취하는 액션은 $x$번째 위치의 $x$개 돌을 없애고 $x-1$번째 위치부터 $1$번째 위치까지의 모든 돌 개수를 $1$ 증가시키는 것이라고 해보자.

 

$W_2 \to V$일 때 취하는 액션은 $y$번째 위치의 $y$개 돌을 없애고 $y-1$번째 위치부터 $1$번째 위치까지의 모든 돌 개수를 $1$ 증가시키는 것이라고 해보자.

 

우선 $W_1 \neq W_2$이므로, $x = y$이라면 나오는 상태 $V$도 다르므로, $x \neq y$이다. 따라서 일반성을 잃지 않고 $x < y$라고 해보자.

 

그러면 $W_1 \to V$에서 나온 결과 $V$에서 $x$번째 위치의 돌 개수는 $0$개인데, $W_2 \to V$에서 나온 결과 $V$에서는 $x$번째 위치의 돌 개수는 $0$개보다 무조건 크다. ($y > x$이므로 무조건 $1$개는 있다)

 

따라서 이런 결과를 만족시키는 $x$와 $y$는 존재하지 않으므로, 결국 $W_1 = W_2$, 즉, $N = k+1$일 때 이기는 상태는 유일함을 확인할 수 있다.

 

 

이제 작은 예시들($N = 8$까지)을 통해 직접 해 구성의 원리를 파악해보자.

 

$N = 1$일 때의 해답은 $(1)$이다.

 

$N = 2$일 때의 해답은 $(0, 2)$이다.

 

$N = 3$일 때의 해답은 $(1, 2)$이다.

 

$N = 4$일 때의 해답은 $(0, 1, 3)$이다.

 

$N = 5$일 때의 해답은 $(1, 1, 3)$이다.

 

$N = 6$일 때의 해답은 $(0, 0, 2, 4)$이다.

 

$N = 7$일 때의 해답은 $(1, 0, 2, 4)$이다.

 

$N = 8$일 때의 해답은 $(0, 2, 2, 4)$이다.

 

 

$N = 4$에서 $N = 3$인 경우로 넘어갈 때를 잘 보면, $3$번째 위치의 돌을 없애서 $3$번째 위치의 돌이 $0$개가 되었고, 나머지 $1$번과 $2$번 위치의 돌 개수가 $1$개씩 늘어났다.

 

우리가 원하는 것은 역으로 $N = 3$인 경우에서 $N = 4$인 경우를 만들어 내는 것이다.

 

2번 아이디어에 의하면 액션을 취하면 $k$번째 위치의 돌 개수가 $0$개가 되고 $1$번부터 $k-1$번까지 분배되므로, 역으로 액션을 취하면 돌 개수 $0$개인 위치가 $k$번째인 경우, 돌 개수가 $k$가 되고, 해당 위치보다 작은 모든 돌들의 개수는 $1$ 줄어들게 된다.

 

즉, $N = 3$인 경우가 $(1, 2)$이고, 여기서 역액션을 취하면 가장 먼저 만나는 $0$의 위치는 $3$번째 위치이므로, 해당 위치의 돌 개수는 $3$개, 이 위치보다 작은 위치의 돌 개수들을 모두 $1$개씩 줄여서 $(0, 1, 3)$이 $N = 4$인 경우가 되는 것이다.

 

이를 DP처럼 저장하면서 계속해서 $N = 2000$까지 미리 구해놓으면 된다.

 

보드판의 개수가 $80$을 넘지 않는다는 사실이 문제에서 주어져있으므로, 이를 이용하여 $DP[2000][80]$짜리 배열을 미리 선언해놓고, $N = k$일 때의 상황을 $DP[k]$와 같이 저장했다.

 

마지막으로, 10개씩 끊어서 출력해야하므로 출력 형식에도 유의하여 출력하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 10435번 Mancala
# 게임이론, 구성적
'''
접근 방법:
수학적 귀납법으로 생각해보자.
매 순간 전체 돌은 1씩 줄어든다.
N = 1일때의 포지션은 1이다.
N = k일때의 포지션에서 어떤 액션을 취하면 N = k-1인 포지션으로 갈 것이다.
이를 만족하는 포지션을 찾도록 N = k인 포지션을 찾아보자.
'''
import sys
input = sys.stdin.readline

winning_position = [[0 for _ in range(81)] for _ in range(2001)]
winning_position[1][0] = 1
for N in range(2, 2001):
    # 이전 Winning position에서 가장 처음으로 등장하는 0의 위치를 찾는다.
    idx = winning_position[N-1].index(0)
    # 그 위치에 K를 넣는다.
    winning_position[N][idx] = idx+1
    # idx보다 작은 인덱스의 모든 원소들은 이전 winning position의 같은 인덱스의 원소보다 1 작다
    for j in range(idx):
        winning_position[N][j] = winning_position[N-1][j] - 1
    # idx보다 큰 인덱스의 모든 원소들은 이전 winning position의 같은 인덱스의 원소와 같다.
    for j in range(idx+1, 81):
        winning_position[N][j] = winning_position[N-1][j]
P = int(input())
for _ in range(P):
    case_num, N = map(int, input().split())
    idx = 0
    for i in range(80, -1, -1):
        # 마지막으로 0이 아닌 원소가 나오는 인덱스 찾기
        if winning_position[N][i] != 0:
            idx = i
            break
    print(case_num, idx+1)
    ans = winning_position[N][:idx+1]
    for i in range(len(ans)):
        print(ans[i], end = ' ')
        if i % 10 == 9:
            print()
    if len(ans) % 10 != 0:
        print()