[BOJ] 백준 11867번 : 박스 나누기 게임 (JAVA)

문제

박스 나누기 게임은 두 박스를 이용해서 하는 게임이다.

 

처음에 한 박스에는 돌이 N개, 다른 박스에는 돌이 M개 들어있다. 두 사람은 턴을 번갈아가면서 게임을 진행한다.

 

각 사람은 박스를 하나 선택하고, 박스안에 들어있는 돌을 모두 비운다. 그 다음, 다른 박스에 들어있는 돌을 적절히 두 박스로 분배한다. 이때, 두 박스에는 돌이 적어도 1개 이상 있어야 한다.

 

두 박스에 돌을 각각 1개씩 만드는 사람이 게임을 이기게 된다.

 

N과 M이 주어진다. 두 사람이 게임을 완벽하게 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 100, N과 M이 모두 1인 경우는 없다)

 

 

출력

게임을 먼저 시작한 사람이 게임을 이기면 A를, 그 다음에 시작한 사람이 게임을 이기면 B를 출력한다.

 

 

풀이

다이나믹 프로그래밍을 이용한 게임 이론 문제였습니다.

 

 

특정 박스를 모두 비우고 남은 박스에 있는 돌을 나누어서 두 박스에 넣고, 각각의 박스의 돌이 1개가 되도록 만드는 사람이 이기는 규칙이었습니다.

 

 

N이 M보다 작다고 가정하고, 작은 수부터 천천히 나열해 봅시다.

 

 

(1, 1) -> 기저 사례이므로 A가 승리합니다.

 

 

(1, 2) -> 1번째 박스를 비우고, 2번째 박스로 돌을 나누면 (1, 1). 이것은 기저 사례이므로 A가 승리합니다.

 

 

(2, 2) -> 1번째나 2번째 박스를 비우고, 나머지 하나의 박스로 돌을 나누면 (1, 1). 이것은 기저 사례이므로 A가 승리합니다.

 

 

(1, 3) -> 2번째 박스로 돌을 나누면 (1, 2). 다시, B가 (1, 2)를 (1, 1)로 나눔으로써 B가 승리합니다.

여기서, (1, 2)는 A가 이기는 상황입니다. (앞의 (1, 3)은 고려하지 않고, 단순히 (1, 2)라는 상황만 본 것임을 유의해 주세요.)

 

 

(1, 4) -> 2번째 박스로 돌을 나누면 (1, 3) 또는 (2, 2).

- (1, 3)에 대해서 B가 (1, 2)로 나누면 A가 (1, 1)로 나눔으로써 A가 승리합니다.

여기서, (1, 3)은 A가 지는 상황입니다.

 

- (2, 2)에 대해서 B가 (1, 1) 나누면 B가 승리합니다.

여기서, (2, 2)는 A가 이기는 상황입니다.

 

 

최종적으로 A는 (1, 3)으로 돌을 나눔으로써 승리할 수 있습니다.

 

 

위의 과정을 정리하면, 아래와 같습니다.

 

 

<A가 승리하는 경우>

1. 다음 게임의 상황들 중 하나라도 A가 패배하는 상황.

2. 다음 게임의 상황들 중 기저 사례가 있는 경우.

 

 

<B가 승리하는 경우>

1. 다음 게임의 모든 상황이 A가 승리함. (단, 기저 사례는 제외.)

 

 

이제, A와 B의 승패 규칙을 찾았습니다.

나머지는 메모이제이션을 활용한 다이나믹 프로그래밍을 수행하시면 됩니다.

아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.