스프라그-그런디 정리 (20) 썸네일형 리스트형 [Python] 8845번 Gra https://www.acmicpc.net/problem/8845 8845번: Gra Dla każdej konfiguracji początkowej w osobnej linii wypisz "W", jeśli Hektor wygra grę przy danym ustawieniu, "P" w przeciwnym przypadku. www.acmicpc.net 23/05/31 스프라그-그런디 정리가 적용되는 게임은 DAG(Directed Acyclic Graph)로 모델링 될 수 있다는 사실을 알고 있다면 쉽게 풀 수 있는 문제이다. 비슷한 문제들로 다음과 같은 문제들을 추천하니, 풀어본다면 좋은 연습이 될 것이다. https://www.acmicpc.net/problem/10363 10363번: Circ.. [Python] 16887번 루트 님 게임 https://www.acmicpc.net/problem/16887 16887번: 루트 님 게임 첫째 줄에 돌 더미의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 둘째 줄에 돌 더미에 포함된 돌의 개수 Ai(1 ≤ Ai ≤ 1,000,000,000,000)가 주어진다. www.acmicpc.net 23/04/06 스프라그-그런디 문제로, 사실 스프라그-그런디 정리를 곁들인 수학 문제라고 봐도 무방한 문제다. 그런디 수를 구하는 경계가 조금 구하기 귀찮기 때문에 난도가 높은 것이라고 생각한다. 하지만 개인적으로 플레티넘 1을 받을 정도의 난이도는 아니라고 생각하는 문제다. 문제 접근 방식: 문제에서 주어진 것 처럼 그대로 구현하면 당연히 시간 초과가 날 것이다. 이는 직접 해보면 잘 알 것이다.. .. [Python] 19114번 Master Zhu and Candies (증명 추가 필요) https://www.acmicpc.net/problem/19114 19114번: Master Zhu and Candies Master Zhu puts $n$ heaps of candies on the table. Two players are playing the following game: on their turn, each player can either pick any positive number of candies from the same heap, or split some heap into three smaller non-empty heaps. Player who p www.acmicpc.net 23/05/03 전형적인 스프라그-그런디 정리 문제로, 문제에서 주어지는 그대로 착실하게 구현하면 된.. [Python] 스프라그-그런디 정리 활용 문제 모음 2022.11.01 - [백준 문제 풀이] - [Python] 13034번 다각형 게임 / 16187번 Game on Plane [Python] 13034번 다각형 게임 / 16187번 Game on Plane https://www.acmicpc.net/problem/13034 13034번: 다각형 게임 N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다 lighter.tistory.com 2022.11.01 - [백준 문제 풀이] - [Python] 16895번 님 게임 3 / 7685번 Nim [Python] 16895번 님 게임 3 / 7685번 Nim https://www.acmicpc.net/probl.. [Python] 27306번 DAGame https://www.acmicpc.net/problem/27306 27306번: DAGame 첫 번째 줄에 노드의 개수를 나타내는 정수 $N$ ($2 \le N \leq 500$), 간선의 개수를 나타내는 정수 $M$ ($1 \leq M \leq 100\,000$)이 주어진다. 두 번째 줄 부터 $M$개의 줄에 서로 다른 두 정수 $p$, $q$ ($1 \leq p$ www.acmicpc.net 23/05/03 스프라그-그런디 정리에 대한 이해도가 있어야 해결할 수 있는 문제다. 몇몇 사람들은 스프라그-그런디 정리의 문제를 풀 때 결과만 외우고 그냥 XOR계산만 적용해서 문제를 푸는 경우가 좀 있다고 생각한다. 나도 스프라그-그런디 정리를 적용한 문제를 처음 풀었을 때, 이해 없이 결과만 받아들이고 문.. [Python] 16886번 나누기 게임 https://www.acmicpc.net/problem/16886 16886번: 나누기 게임 구사과와 큐브러버는 나누기 게임을 하려고 한다. 이 게임은 돌이 N개 포함되어 있는 돌 더미 1개에서 시작한다. 두 사람은 턴을 번갈아 가지며, 구사과가 턴을 먼저 갖는다. 각 턴마다 다음을 할 www.acmicpc.net 22/11/19 2022.11.22 - [백준 문제 풀이] - [Python] 2737번 연속 합 [Python] 2737번 연속 합 https://www.acmicpc.net/problem/2737 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acm ligh.. [Python] 16340번 Split Game https://www.acmicpc.net/problem/16340 16340번: Split Game For a long time, rich clientele of Binary Casino has been requesting a new way to gamble their money. To fulfill their wishes, the director of Binary Casino decided to introduce a new game called Split Your Tokens. This game is played only when a customer www.acmicpc.net 22/11/13 전형적인 게임이 분할된 상황에서의 그런디 수를 구하는 문제로, 스프라그-그런디 정리를 충실하게 공부했다면 쉽.. [Python] 7787번 빨간 칩, 초록 칩 https://www.acmicpc.net/problem/7787 7787번: 빨간 칩, 초록 칩 이 게임은 빨간 칩 r개와 초록 칩 g개를 책상 위에 놓고 진행한다. 두 플레이어 A와 B는 턴을 번갈아가면서 게임을 하며, A가 먼저 시작한다. 게임의 규칙은 간단하다. 자신의 턴이 돌아오면 두 색 www.acmicpc.net 22/11/10 스프라그-그런디 정리를 이용해서 풀 수 있는 문제로, 규칙을 찾아서 쉽게 풀 수 있다. 근데 증명하는건 굉장히 어렵다... 증명하는 과정을 한번 살펴보자. 문제 접근 방식: 그런디 수를 구하는 방법으로 그런디 수를 계속 재귀적으로 20개까지 구하다 보면 아래와 같은 규칙을 발견할 수 있다. (20개까지의 그런디 수는 알아서 구해보자) 만약 칩 개수를 2로 나누었을 때.. 이전 1 2 3 다음
