게임 이론 (31) 썸네일형 리스트형 [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로 나누었을 때.. [Python] 11869번 님블 https://www.acmicpc.net/problem/11869 11869번: 님블 님블은 1×N 직사각형에서 즐기는 게임이다. 직사각형은 1×1 크기의 정사각형으로 나누어져 있고, 가장 왼쪽 정사각형은 0번, 그 오른쪽 정사각형은 1번, ..., 가장 오른쪽 정사각형은 N-1번이다. 각 www.acmicpc.net 22/10/13 그냥 다른 게임을 가장한 nim게임으로, nim게임 풀듯이 풀면 된다. 문제 접근 방식: 그냥 모든 숫자들을 xor 하면 끝이다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다. 더보기 # 11869번 님블 # 게임이론, 스프라그-그런디 정리 ''' 그냥 nim게임임 ''' N = int(input()) total = 0 nu.. [Python] 16899번 채석장 게임 https://www.acmicpc.net/problem/16899 16899번: 채석장 게임 첫째 줄에 채석장의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 채석장의 정보가 주어진다. 채석장의 정보는 두 정수 Xi, Mi (1 ≤ Xi, Mi ≤ 1016)로 이루어져 있다. www.acmicpc.net 22/10/13 전형적인 nim게임으로, 그냥 XOR을 하면 시간 초과가 나는 문제이다. XOR연산의 성질을 이용해야 풀 수 있는 영리한 문제이다. 문제 접근 방식: 문제의 조건을 자세히 살펴보면, N의 크기가 최대 10만이고, Mi가 최대 10의 16승까지 있으므로, 그냥 모든 숫자들을 XOR 연산시키려고 한다면 무조건 시간 초과가 난다. https://www.acmicp.. [Python] 16895번 님 게임 3 / 7685번 Nim https://www.acmicpc.net/problem/16895 16895번: 님 게임 3 구사과와 큐브러버가 님 게임을 하고 있다. 님 게임은 돌을 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진 www.acmicpc.net https://www.acmicpc.net/problem/7685 7685번: Nim The input test file will contain multiple test cases, each of which begins with a line indicating the number of piles, 1 ≤ n ≤ 1000. On the next line, there are n positive .. [Python] 13034번 다각형 게임 / 16187번 Game on Plane https://www.acmicpc.net/problem/13034 13034번: 다각형 게임 N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다. 성관이와 홍준이는 다각형에서 게임을 하려고 www.acmicpc.net https://www.acmicpc.net/problem/16187 16187번: Game on Plane You are given $N$ points on a plane. These points are precisely the set of vertices of some regular $N$-gon. Koosaga, an extreme villain, is challenging you with .. 이전 1 2 3 4 다음