문제 링크 1. 아이디어 스프라그 그런디 정리를 통해 해결할 수 있는 문제로 두 돌이 서로 가까워지는 방향으로만 이동한다고 했을 때, 그런디 수를 구하면 두 돌 사이의 간격을 님 게임의 돌 더미의 돌의 개수와 동일하게 볼 수 있으니 $g(n) = n - 2$ 가 된다. 해당 문제는 돌이 서로 멀어지는 방향으로도 이동할 수 있는데 이때 내 돌...

문제 링크 1. 아이디어 주어진 출력에 맞게 재귀 함수를 구성하면 되는 문제로 재귀 깊이만큼 앞에 언더 바를 출력하는 점만 유의하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; public class Main { static BufferedWriter bw = new BufferedWrit...

문제 링크 1. 아이디어 N개의 꼭짓점으로 이루어진 볼록 다각형에서 선분이 교차하기 않게 그을 때 마지막에 그어서 이기는 플레이어를 찾는 문제로 스프라그 그런디 정리를 활용하면 해결할 수 있다. N개의 꼭짓점으로 이루어진 볼록 다각형에서 임의의 선분을 처음 그었을 경우 해당 선분을 기준으로 점들이 양쪽으로 나뉜다. 선분이 교차할 수 없으므...

문제 링크 1. 아이디어 님 게임에서 돌을 제거하는 대신 두 개의 돌 더미로 나누는 방법이 추가된 문제로 스프라그 그런디 정리를 활용하면 해결할 수 있다. 먼저 그런디 수를 구해야 하는데 님 게임처럼 돌을 제거하는 방법은 항상 가능하므로 그런디 수를 $g(n)$ 이라 할 때, $g(n)$ 은 $g(0)$ 부터 $g(n - 1)$ 까지는 고려...

문제 링크 1. 아이디어 재귀를 처음 배울 때 자주 나오는 유명한 하노이 탑 문제로 이동 횟수와 순서를 출력해야 한다. 하노이 탑은 1번에서 3번으로 모든 원판을 이동하기 위해 가장 아래 원판을 제외한 나머지 원판들을 2번으로 옮긴 후 가장 아래 원판을 3번으로 옮기고 다시 2번으로 옮긴 원판들을 3번으로 옮기면 된다. 이때 현재 하노이 탑...

문제 링크 1. 아이디어 2차원 배열의 특정 좌표를 Z모양으로 탐색 시 몇 번째로 방문하는지 구하는 문제로 분할 정복을 활용하면 해결할 수 있다. 현재 바라보는 배열을 중앙을 기준으로 십자 모양으로 분할했을 때, 각 영역은 한 단계 작은 2차원 배열을 동일하게 Z모양으로 탐색하는 꼴이라서 재귀로 풀어낼 수 있으며 좌표 정보가 주어지므로 해당...

문제 링크 1. 아이디어 K의 제곱수만큼의 금화를 가져갈 수 있을 때 승리할 수 있는 해적을 구하는 문제로 그런디 수의 규칙성을 통해서 해결했다. 먼저 K가 홀수인 경우 홀수의 제곱수는 모두 홀수이므로 두 해적이 서로 홀수 개의 금화를 가져가게 되고 이는 남은 금화의 홀짝이 계속 바뀌게 된다. 따라서 초기 금화의 개수가 홀수면 선공이 이기며...

문제 링크 1. 아이디어 님 게임에서 선공 플레이어가 이기기 위해 할 수 있는 방법의 수를 구하는 문제로 선공에서 게임을 이기려면 Nim-Sum을 0으로 만들어 후공의 악수를 강요해야하므로 첫 턴에 Nim-Sum을 0으로 만들 수 있는 경우의 수를 구하는 것과 같다. Nim-Sum이 $nim = p_1 \oplus p_2 \oplus p_...

문제 링크 1. 아이디어 님 게임과 유사한데 돌을 가져갈 때 피보나치 수에 해당하는 수만큼만 가져갈 수 있다. 스프라그 그런디 정리를 활용해 각 돌 더미에 돌의 개수에 대한 그런디 수의 XOR 값으로 승패를 판단할 수 있다. 그런디 수를 구하기 위해 먼저 3×10⁶ 이하인 모든 피보나치 수를 구해줬다. 그런디 수의 경우 규칙이 크게 보이지...

문제 링크 1. 아이디어 님 게임에서 홀짝 규칙이 추가된 게임으로 짝수 개수만큼 돌을 제거하는 경우는 돌 더미의 모든 돌을 제거할 수 없고, 홀수 개만큼 돌을 제거하는 경우는 돌 더미의 모든 돌을 제거해야 한다. 해당 문제는 돌 더미의 돌의 개수를 약간 조작하면 님 게임과 동치인 게임으로 만들 수 있는데 돌 더미의 돌이 짝수 개인 경우 돌...