C/C++로 알아보는

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

풀이

애드 혹 태그가 달린 문제답게 풀이도 코드도 간단했지만 풀이를 얻기까지 한두시간 고민했다.

실제 풀이에서 맨 처음 생각한 아이디어는 우선 문자의 쌍을 찾아야 한다는 것이다. 예를 들어 U를 입력하면 그에 대응되는 S가 어딘가에 존재한다. 이런 경우 누적 합을 통해 구간을 관리할 수 있다. BOJ1023(괄호 문자열)과 비슷한 맥락에서 두 부분문자열을 연결한 문자열도 동일하게 해결할 수 있으므로 반대로 원래 문자열을 문제의 조건을 만족하는 두 부분문자열로 컷 한 뒤 해결하는 방법을 생각해봤다.

우선 예제 입출력을 분석해보자. 예제 입출력에서 발견한 특징은 "정답 문자열 제일 끝에 불필요한 N이 붙어있다. 그것도 두개씩이나."였다. 

예제 출력을 따라가면 입력의 문자열을 "뒤에서부터" 구성한다는 것을 알 수 있었다. 예컨대 예제 입력 1은 SS로도 작성할 수 있지만, 뒤에서부터 작성하면  SNNS로 작성하게 된다.

실제로 뒤에서 부터 작성하려는 아이디어를 떠올렸을 때 문뜩 든 생각은 앞서 생각한 문자 쌍을 찾기 아주 쉽다는 것이다. 최소해를 찾는 경우가 아니기때문에 문자 쌍이 대응되는 것이 유일할 필요가 없고, 아무거나 적당히 문자 쌍을 대응시킬 수 있다면(풀이 과정 중의 해의 성질을 여전히 만족하는 이상), 대응시키면 된다. 실제로 이 시점에서 문제의 풀이가 완성되었고, 바로 코드를 작성해서 AC를 받았다. 물론 코드를 작성하는 과정에서 어림으로 계산했던 디테일을 잡아갔다.

일단 최초 상태를 빈 문자열 가장 뒤에 커서가 위치한 것으로 볼 수 있다. 가장 뒤의 문자가 S라고 가정하자. 이 문자는 자명하게 U를 입력해 나온 S여야 한다. 따라서 이 S와 대응되는 U가 앞선 문자열의 일부에 존재한다. 만약 이 이전 문자가 U라고 가정하면, 즉 가장 마지막 두 글자가 US라면 이 두 글자를 제외한 나머지 앞선 부분문자열은 본 알고리즘으로 풀 수 있다. 따라서 UNN을 시행하면 마지막 US를 오른쪽에 입력하고 나머지 문자열을 입력하기 위해 US를 제외한 나머지 빈 문자열 가장 뒤에 위치시킨 것과 같다. 다르게 말하면, US를 가장 오른쪽에 입력하고 나머지 부분문제를 풀기 위한 최초상태로 진입하는 것이다.

앞서 생각했던 괄호 문자열과 비슷하게 입력을 분석해보자. US, SU는 입력할 수 있는 문자열이다. 입력할 수 있는 두 문자열 S, T에 대해 ST도 입력할 수 있는 문자열이고, UTS, STU도 입력할 수 있는 문자열이다. 어떤 부분문자열 T를 입력하고 난 뒤 커서를 가장 왼쪽에 위치할 때 까지 N을 실행하고, 다시 부분문자열 S를 입력하면 ST를 출력할 수 있고, UN을 실행하고 T를 입력하면 UTS, SN을 실행하고 T를 입력하면 STU도 입력할 수 있다.

이 로직에서 커서를 우선 어떤 문자 왼쪽으로 이동시키고 나면 커서 오른쪽 문자열은 어떤 일이 있어도 수정될 수 없다. 따라서 커서 오른쪽 문자열을 입력마다 추적해보자. 커서의 위치를 C로 쓰자. UNUNNN의 경우 "USC" -> "UCS" -> "UUSCS"-> "UUCSS"-> "UCUSS" -> "CUUSS"와 같이 작성된다. 이때 N이 하나 추가될 때마다 커서가 한 칸 왼쪽으로 이동한다. 반대로, N이 하나 추가될 때마다 커서 오른쪽에 문자가 하나 추가된다. 우리가 원하는 로직이 문자를 입력한 뒤 커서를 이미 입력한 문자 왼쪽으로 보내는 것이기 때문에 N을 문자열 길이만큼 입력해야 한다.

실제로 이를 재귀로 실행할 필요는 없다. 두 부분문자열이 연속해서 등장하는 경우는 N을 출력해 커서의 위치를 이동한 뒤 출력하면 되고, STU, UTS의 경우는 UN(또는 SN)을 실행한 뒤 커서 왼쪽의 부분문자열을 보면 S(또는 U)가 하나 U(또는 S)보다 하나 많은 부분문자열이 된다. 이때 입력할 수 있는 문자열을 오른쪽부터 입력하고 난 뒤 S(또는 U)를 만난다면 가장 앞선 문자와 쌍을 이루는 문자라고 생각할 수 있으므로 N을 실행하면 UTS, STU의 문자열을 입력하고 커서를 왼쪽 끝으로 이동시킬 수 있다. 좀 더 자세히 얘기하자면, 오른쪽에서 왼쪽으로 훑으면서 커서 오른쪽의 문자열이 입력가능한 문자열일 때 처음 만난 문자와 대응되는 S<->U는 이 두 문자를 제외하고 입력가능한 문자열이 지난 후에 처음으로 나오는 대응되는 문자인 경우는 해가 된다.

설명이 길었는데, 실제 로직은 아래와 같이 해결된다.

1. 가장 오른쪽 문자부터 순서대로 확인한다. S에 1, U에 -1을 대응시키자. 오른쪽에서 왼쪽으로 이동하면서 문자열의 누적합을 구하자. 누적합이 0이라면 이전까지 탐색한 문자열이 입력가능한 문자열이라는 뜻이다. (문제 조건에서 해가 존재함을 증명가능하다고 서술했다.)

2. 현재 만난 문자가 S이고 누적합이 0 이상이라면 UN을 출력한다.

3. 현재 만난 문자가 U이고 누적합이 0 이하라면 SN을 출력한다.

4. 현재 만난 문자가 S이고 누적합이 음수이거나, 현재 만난 문자가 U이고 누적합이 양수라면 N을 출력한다.

이렇게 완성된 문자열은 N이 문자열 길이만큼 존재하고 문자열 길이의 절반만큼 U나 S를 입력해야 하므로 정확히 3/2N개의 길이가 된다.

뭐라 설명하기는 어렵지만 순서대로 따라가면 해가 되겠거니하는 생각은 쉽게 할 수 있을거라고 생각한다. 애드혹 문제들이 설명하거나 유도하는 과정을 말로 설명하기는 어렵지만 로직을 짰을 때 타당하다고 확인하기 쉬운 문제들인 것 같다.

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

관점을 바꿔서 어떤 공장에서 라면을 구매하는 가격을 책정하는 문제로 바꿔보자. 한 공장에서 라면을 구매하는 방법은 3원을 주고 구매하는 방법과 특정 조건이 만족되면 2원을 주고 구매하는 방법의 두 방법 뿐이다. 당연히 한 공장에서 라면을 구매하기 위해서는 2원에 구매할 수 있는만큼 구매하는 것이 최적해이다.
첫번째 공장에서는 이전 공장이 하나도 없으므로 무조건 3원에 라면을 모두 구매해야 한다. 따라서 유일한 방법인 3원에 모두 구매하는 것이 최적해이고, 이후에 다른 공장에서 구매하는 것과 관계없다. 두번째 공장에서는 최대 첫번째 공장에서 3원에 구매한 라면의 수만큼 2원에 구매할 수 있고, 나머지는 모두 3원에 구매해야 한다. 두번째 공장에서 3원에 구매했거나, 첫 번째 공장에서 3원에 구매한 것을 토대로 두 번째 공장에서 2원에 구매한 개수만큼 세 번째 공장에서 2원에 구매할 수 있다.
세 번째 공장 이후의 2원에 구매할 수 있는 라면의 최대 개수는 i번째 공장에 대해 min(i-2번째 공장에서 3원에 구매한 라면 개수,i-1번째 공장에서 2원에 구매한 라면 개수)+i-1번째 공장에서 3원에 구매한 라면 개수가 된다.
좀더 일반적으로 두 번째 공장의 경우 i-2번째 공장에서 구매한 라면의 총 개수가 0이라 두면 동일한 계산이 되고, 첫 번째 공장도 i-1, i-2번째 공장에서 라면을 0개 구입한 것과 동일하다.

따라서 존재하지 않는 공장에서 구매한 개수를 0이라 강제하고 min(i-2번째 공장에서 3원에 구매한 라면 개수,i-1번째 공장에서 2원에 구매한 라면 개수)+i-1번째 공장에서 3원에 구매한 라면 개수를 이용해 DP를 돌리는 것으로 해결 가능하다.

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

크기 L인 부분구간의 최솟값을 모두 찾는 문제이다. 처음 봤을때는 슬라이딩 윈도우로 풀어야 할 것 처럼 생겼다. 

"최솟값을 아주 빠르게 찾을 수 있고, 원하는 값을 아주 빠르게 제거할 수 있는" 자료구조가 있으면 된다. 일단 슬라이딩 윈도우로 작은 크기의 문제를 풀어보자. 시간복잡도는 O(N*L)이다.

예제의 앞 10개항이다.

이제 관찰을 해보자. 슬라이딩 윈도우 안에 삽입된 수열의 항은 L번의 최솟값 산출 후 제거된다. 이 슬라이딩 윈도우에 삽입된 수는 삽입된 순서대로 제거된다. 즉, 큐를 이용해 해결할 수 있을 것으로 보인다. 

D3을 구할 때 5 뒤에 2가 삽입되었다. 5는 2보다 먼저 제거되는데, 제거되기까지 슬라이딩 윈도우에는 5보다 작은 2가 항상 존재하므로 5는 답이 될 수 없다. 따라서, D3을 구할 때 굳이 5가 슬라이딩 윈도우 안에 있을 필요가 없다. 따라서 위의 해결과정을 살짝 수정하자. 

이 과정을 보편적으로 설명하면, 슬라이딩 윈도우 중 현재 단계에서 새로 삽입될 수 보다 작은 값을 미리 제거할 수 있다는 것이다. 즉, 슬라이딩 윈도우의 가장 마지막 항 보다 큰 수는 슬라이딩 윈도우에서 미리 제거할 수 있다. 하지만, 이 과정을 전 과정에 동일하게 적용한다면, 가장 뒤의 원소를 삽입하기 이전에도 이전의 가장 마지막 항보다 큰 수는 슬라이딩 윈도우 안에 없고, 귀납적으로 슬라이딩 윈도우는 정렬되어있다.

정렬되어있는 슬라이딩 윈도우는 큰 값이 뒤에 위치한다. 이때 이 슬라이딩 윈도우의 제일 뒤에 값을 삽입하려한다. 이때 새로 삽입되는 숫자보다 큰 숫자가 존재한다면, 슬라이딩 윈도우의 제일 끝의 원소는 새로 삽입될 숫자보다 자명하게 크다. 따라서 가장 마지막 원소를 제거하고 다시 판단하면 된다. 즉, 슬라이딩 윈도우의 가장 나중에 삽입된 원소를 제거하는, 스택의 쿼리도 지원해야 한다.

이 슬라이딩 윈도우가 제공해야 할 쿼리는 제일 앞의 원소를 제거하고, 제일 위의 원소를 추가하거나 제거하는 쿼리이고, 덱으로 쉽게 구현할 수 있다.

정리하면, i번째 항 Ai를 슬라이딩 윈도우에 추가하기 위해서, Ai-L을 슬라이딩 윈도우에서 제거한다. 이 제거과정은 삽입되는 순서대로 원소를 제거하는 과정이므로 덱의 제일 앞에 있거나 그 전에 이미 제거되었을 것이다. 따라서 덱의 제일 앞에 있는 경우에는 제거하고, 아니면 그냥 넘어간다. Ai를 추가하기 전, 덱의 제일 뒤에서 Ai보다 큰 값들을 모두 제거한다. 그리고 Ai를 덱에 넣고, 제일 앞의 값이 Di가 된다.

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

n=1일때는 자명하게 다익스트라로 구할 수 있다. 다익스트라로 1번째 최단경로를 구하는 과정을 다시 곱씹어보자.

이때까지의 모든 방문에 대해 방문하지 않은 모든 정점을 방문하고, 1번째 최단경로를 갱신한다. 이를 적절히 변형해서 k번째까지 구하면 된다.

우선순위 큐에는 아직 갱신되지 않은 적절한 경로들이 들어있다고 하자. 우선순위 큐의 정렬 순서는 경로의 길이이다. 우선순위 큐에서 경로 하나를 pop하자. 이 경로의 최종 정점에 인접한 모든 정점들로 가는 전체 경로들을 우선순위 큐에 넣자. 이렇게 되면 각 최종 정점으로 가는 새로운 경로가 생긴다. 이때 최종 정점 중 한 번 이상 방문한 경우 우선순위 큐에 넣는 과정을 생략하면 1번째 최단경로를 다익스트라를 이용해 구할 수 있다.

일정 횟수 이상 방문을 제한하는 것으로 k번째 최단경로도 쉽게 구할 수 있다. 위 과정에서 방문 횟수가 k 미만인 경우 우선순위 큐에 넣고, k 이상인 경우 넣지 않는 것으로 충분하다.

먼저, 1번 정점으로 가는 길이 0의 경로를 우선순위 큐에 넣고 시작하자. 반복문을 통해 우선순위 큐에서 경로 하나를 pop한다. 그리고 이 정점의 방문횟수를 추가한다. 이 방문횟수는 이 경로가 몇 번째 최단경로인지를 의미한다. 이 정점과 연결된 모든 k번 미만 방문한 정점에 대해 이 경로 뒤에 그 정점을 추가해 우선순위 큐에 집어넣는다. 

이 로직의 정당성은 아래 과정을 통해 보일 수 있다.

1. 경로를 우선순위 큐에 넣고 순서대로 탐색했기 때문에, 정점을 방문할 때 사용한 경로 가운데 k번째 경로를 반환한다.

2. 누락되는 경로는 없다. 만약 존재한다면, 다시말해 적절한 시점에서 우선순위 큐의 경로 길이 length에 대해 우선순위 큐에 한 번도 들어가지 않은 경로 중 length보다 작은 길이의 경로 P가 존재한다면, P의 마지막 정점을 제거한 P-가 우선순위 큐에 들어간 적이 없다는 것이고, P--도 우선순위 큐에 들어간 적이 없다는 것이고, ... 의 과정을 통해 모순을 반환할 수 있다. (1번 정점으로 가는 길이 0의 경로를 넣은 적 없다는 결론을 얻을 수 있으므로)

3. k번을 초과하여 정점 A를 방문한 뒤 B를 방문하는 경로는 B를 k번 이하 방문하는 경로일 수 없다. A를 방문한 뒤 B를 방문하는 k개의 경로가 더 짧은 경로가 되기 때문이다.

마지막으로 경로의 모든 과정을 우선순위 큐에 넣을 필요는 없다. 따라서 경로의 길이와 최종 방문한 정점만 우선순위 큐에 넣는 것으로 해결가능하다.

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

풀이

자명하게, 맹독 방벽은 건물들의 Convex Hull보다 L이상 떨어져 있어야 한다.

Convex Hull에서 L만큼 떨어진 점들을 모두 모은 폐곡선의 길이를 생각해보자.

Convex Hull에서 L 만큼 떨어진 점들은 Convex Hull을 이루는 선분을 바깥으로 L만큼 평행이동한 부분(위 그림의 검은 선분)을 포함하고, 나머지 부분은 꼭짓점에서 L만큼 떨어진 호(위 그림의 붉은 곡선)가 된다. 이때 검은 선분의 길이 총합은 Convex Hull의 둘레와 같고, 붉은 곡선은 모든 방향의 partition이므로(검은 선분의 양 끝과 Convex Hull의 꼭짓점을 이으면 직사각형이 되고, 평행사변형이므로 붉은 두 선분은 서로 평행하기 때문) 반지름 L인 원의 원주가 된다.

Convex Hull을 찾아 둘레를 구하고, L에 3.1415926*2를 곱한 값을 더해 답을 얻을 수 있다.

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

문제

초라기는 한국의 비밀국방기지(원타곤)를 습격하라는 임무를 받은 특급요원이다. 원타곤의 건물은 도넛 형태이며, 초라기는 효율적인 타격 포인트를 정하기 위해 구역을 아래와 같이 두 개의 원 모양으로 나누었다. (그림의 숫자는 각 구역의 번호이다.)

초라기는 각각 W명으로 구성된 특수소대를 다수 출동시켜 모든 구역에 침투시킬 예정이며, 각 구역 별로 적이 몇 명씩 배치되어 있는지는 초라기가 모두 알고 있다. 특수소대를 아래 조건에 따라 침투 시킬 수 있다.

1. 한 특수소대는 침투한 구역 외에, 인접한 한 구역 더 침투할 수 있다. (같은 경계를 공유하고 있으면 인접 하다고 한다. 위 그림에서 1구역은 2, 8, 9 구역과 서로 인접한 상태다.) 즉, 한 특수소대는 한 개 혹은 두 개의 구역을 커버할 수 있다.
2. 특수소대끼리는 아군인지 적인지 구분을 못 하기 때문에, 각 구역은 하나의 소대로만 커버해야 한다.
3. 한 특수소대가 커버하는 구역의 적들의 합은 특수소대원 수 W 보다 작거나 같아야 한다.

이때 초라기는 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 알고 싶어 한다.

풀이

2*n타일링처럼 풀면 된다. 단, 1칸짜리 블럭을 사용한다는 점과 원형이라는 점을 생각해 줘야 한다. 

길이가 2인 방향을 세로, n인 방향을 가로라고 하자.

블럭을 어떻게 쌓을 수 있을까를 생각해 보자. 가로방향으로 이동하면서 DP배열을 채워나간다.

바깥에 있는 구역은 어떤 구역과도 연결되어있지 않거나 안쪽 구역과 연결되어있거나 왼쪽 구역과 연결되어있거나 오른쪽 구역과 연결되어있을 수 있다. 반대로, 어떤 구역과도 연결되어있지 않거나 안쪽에 있는 구역은 바깥쪽 구역과 연결되어있거나 왼쪽 구역과 연결되어있거나 오른쪽 구역과 연결되어있을 수 있다. 안쪽 구역이 바깥쪽 구역과 연결되어있다면 같은 세로줄의 바깥쪽 구역은 안쪽 구역과 연결되어있어야 하므로 한 개의 세로줄이 가질 수 있는 연결의 방법은 총 10가지이다.

10가지 경우에 대해 다음 DP배열을 채울 때 가능한 연결 방법이 있고 불가능한 방법이 있다. 따라서 가능한 모든 방법을 토대로 DP 배열을 채우면 된다.

마지막으로 모든 배열을 다 채웠다면 첫 번째 세로줄과 마지막 세로줄을 비교하면서 가능한 모든 연결방식의 DP 배열의 값을 더해주면 된다. 

실제로 10가지 모든 경우의 수를 하드코딩해서 해결했다. 

먼저 각 세로줄이 왼쪽과 연결되어있는지, 오른쪽과 연결되어있는지를 크기 10인 배열로 미리 저장해둔다. 바깥쪽이 왼쪽과 연결되어있다면 2, 안쪽이 왼쪽과 연결되어있다면 1, 둘 다 연결되어있다면 3, 둘 다 연결되어있지 않다면 0으로 두고 해결했다. 오른쪽도 마찬가지로 미리 저장해서 해결했다. 

k번째 경우의 수의 왼쪽 모양을 left[k], 오른쪽 모양을 right[k]라고 두면 아래와 같이 미리 모양을 만들어둘 수 있다.

왼쪽의 경우와 오른쪽의 경우를 분리한 이유는 i번째 세로줄과 i+1번째 세로줄이 연결될 수 있는지 확인하기 위해 right[i]==left[i+1]을 바로 이용하기 위해서이다. 0번과 1번의 경우 left와 right가 동일한데, 이를 구분해 줄 방법이 필요하다.

어떤 칸이 왼쪽 또는 오른쪽과 연결되어있는 경우 이를 0.5개의 소대를 사용한다고 생각해도 동일한 답을 얻을 수 있다.

이때 각 세로줄이 연결상태에 따라 사용할 소대의 수를 미리 계산해서 넣어두자. 

소수를 저장하게 되는 것은 마음에 들지 않는다. 두 배 해서 저장해 두고 마지막 최종 답을 구할 때 2로 나누자. 두 배 한 뒤의 최종 답이 홀수가 나오는 경우는 없다.

다음으로 DP배열을 구성하자. 

DP[x][type]=> 마지막이 type으로 끝나면서 x번째 세로줄까지의 최적해라 두면, 

DP[x][type]는 left[type]와 right[pretype]의 값을 같게 만들면서 연결되어  있는 소대의 총원이 W보다 작게 되는 모든 pretype에 대해 DP[x-1][pretype]의 합과 같다.

이런식으로 DP배열을 모두 채운다. 

단, 마지막 세로줄의 경우 DP배열을 채울 때 한가지 더 고려해 줘야할 대상이 있다. 바로 첫 번째 세로줄과 연결할 수 있는지 여부이다. right[x]에 따라 첫 번째 세로줄과 연결했을 때 소대의 총원이 W보다 큰 경우가 있다면 최적해 계산에서 제외해 줘야 한다. 

마지막으로, 이렇게 채워진 DP[N-1] 배열의 최소값을 찾아 "2로 나눈" 값이 정답이 된다.

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

문제.

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 4^x개 만큼 가져갈 수 있다. 즉, 가능한 개수는 1, 4, 16, 64, ...개 이다. 4^x개만큼 돌을 가져갈 수 있는 방법이 없는 사람이 게임을 지게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력.

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

풀이.

상대 플레이어가 돌을 몇 개 가져가던 관계 없이 두 플레이어가 가져가는 돌의 합이 5의 배수가 되도록 할 수 있다.

4^n은 5로 나눈 나머지가 1 또는 -1이기 때문에 상대가 나머지 1인 돌 개수를 가져갔다면 4개를, 상대가 나머지 -1인 돌 개수를 가져갔다면 1개를 가져가는 것으로 해결가능하다.

따라서 탁자 위에 돌의 개수가 4개 이하인 경우만 살펴 주면 되고, 돌의 개수가 0개 또는 2개인 경우가 지는 경우이다. 따라서 n을 5로 나눈 나머지에 따라 답을 출력할 수 있다.

이런 류의 게임에서는 상대가 가져간 돌의 개수와 반대되는 개수를 가져갈 수 있도록 반복 단위를 설정할 수 있다면 쉽게 해결된다.

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

문제.

3개의 돌무더기에 돌이 각각 x,y,z 개 있다. R과 B가 이 돌무더기에서 게임을 한다. 각 플레이어는 다음의 한 가지 시행만을 할 수 있다.

• 돌이 있는 두 개의 돌무더기를 골라, 돌을 하나씩 가져가고, 나머지 하나의 돌무더기에 돌을 하나 추가한다.

더 이상 시행을 할 수 없는 사람이 이긴다.

R와 B가 최선을 다했을 때 이기는 사람을 출력하여라. 게임은 R이 먼저 시작한다.

입력.

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.

다음 T줄에 각각 세 개의 정수 x, y, z가 주어진다.

제한.

•  1≤T≤200000
•  1≤x,y,z ≤10^9

풀이.

x,y,z 범위로 생각했을 때 DP로는 해결 불가능하다.

각 플레이어가 할 수 있는 행동은 다음과 같다.

어...? 각 행동을 할 때 마다 전체 돌의 개수는 1개 줄어든다.

a = x+y, b = y+z, c = z+x로 두자. 그러면 행동에 따른 돌의 개수 변화는 다음과 같다.

문제를 변형해보면, 돌무더기 a, b, c에서 한 번에 두개씩만 가져갈 수 있는 게임이 된다.

각 돌무더기에서는 최대 a/2, b/2, c/2번 가져갈 수 있다. 또, 더 이상 게임을 진행할 수 없다는 것은 "a, b, c중 어느 하나의 돌의 개수가 0인 것"과 같다.

예를 들어 a가 0이 되었다면 a=x+y이고 x, y는 0보다 큰 정수이므로 x=0,y=0이 되기 때문에 원래 문제에서의 "돌이 있는 두 개의 돌무더기를 골라"를 할 수 없기 때문이다. b 또는 c가 2 이상일지라도 z에서 두 개의 돌을 가져갈 수 없다.

따라서 a/2+b/2+c/2-2번 가져가고 나면 그 다음 플레이어는 게임을 진행할 수 없게 된다. 처음 가져가는 플레이어가 R이므로 a/2+b/2+c/2-2가 짝수이면 R, 홀수이면 B가 승리한다.

다시 식을 정리하자. a/2+b/2+c/2=(a+b+c)/2-(a,b,c중 홀수의 개수)/2=(x+y+z)-(x, y, z가 모두 홀수 또는 짝수이면 0, 아니면 1)이고, 이 값의 홀짝 여부에만 종속되므로 (x, y, z의 홀수 개수) - (x,y,z가 모두 홀수 또는 짝수이면 0, 아니면 1)와 같다.

x,y,z의 경우의 수에 대해 표로 정리하면

과 같고, 결과가 홀수일 때 B, 짝수일 때 R이 승리하는 것과 같다.

문제를 보자마자 전체 돌의 개수가 1씩 감소하는 것을 확인하고 더하고 빼고 하다보면 한 돌무더기에서만 돌을 가져가는 문제로 변형할 수 있어 보여 시도해서 정답을 얻었습니다.