게임 이론 (31) 썸네일형 리스트형 [Python] 24553번 팰린드롬 게임 / 31648번 Palindrome Game https://www.acmicpc.net/problem/24553 24553번: 팰린드롬 게임 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1\,000$) 둘째 줄부터 $T$개의 줄에 걸쳐, 돌 무더기에 쌓여 있는 돌의 개수 $N$이 주어진다. ($1 \le N \le 10^{18}$) www.acmicpc.net https://www.acmicpc.net/problem/31648 31648번: Palindrome Game Bessie and Elsie are playing a game with a pile of stones that initially contains $S$ stones ($1\le S= 0 and DP[i-p] == 1: break else: DP[i].. [Python] 18689번 Baklawa https://www.acmicpc.net/problem/18689 18689번: Baklawa Baklawa or baklava, is a sweet middle eastern dessert, mainly made from phyllo dough sheets, walnuts, and sugar syrup cut into small cubic pieces and served in cuboid boxes containing multiple layers. Alice and Bob love to play what they call the last Bakl www.acmicpc.net 23/08/19 전형적인 스프라그-그런디 문제로, 문제의 상황을 님게임으로 변형시키기만 하면 해결할 수 있는 매우 쉬운 문제이다.. [Python] 26074번 곰곰이와 테트리스 https://www.acmicpc.net/problem/26074 26074번: 곰곰이와 테트리스 곰곰이가 첫 차례에 4번째 종류의 블록(2×2 모양)을 그림과 같이 배치하고 20점을 획득하면, 이후 게임이 어떻게 흘러가던 관련 없이 무조건 이길 수 있다. www.acmicpc.net 23/08/24 이전에 곰곰컵 때 이 문제를 풀어보려고 시도했다가 실패했었다. 엄청난 전략이 숨어있는 문제로, 이 글을 보기 전에 충분한 고민을 하기 추천한다. 여담으로 내 1800번째 문제이다. 문제 접근 방식: 이 문제는 겉으로 볼 때 많은 것들을 고려해야 되는 것처럼 보인다. 블록 별로 점수가 다양하게 주어지고, 판의 크기 또한 다양하게 주어지는 상황 속에서 "최적의 행동"을 생각해야 하기 때문이다. 이 문제의 핵심.. [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계산만 적용해서 문제를 푸는 경우가 좀 있다고 생각한다. 나도 스프라그-그런디 정리를 적용한 문제를 처음 풀었을 때, 이해 없이 결과만 받아들이고 문.. 이전 1 2 3 4 다음
