기로에 서다

문제 www.acmicpc.net/problem/12107 12107번: 약수 지우기 게임 1 N=4인 경우, A는 처음에 4,2,1을 지운다. 칠판에 남은 수는 3으로, B는 3을 지울 수밖에 없어 패배한다. www.acmicpc.net 문제 풀이 모든 수의 약수인 1을 제외한 N-1개의 수로 게임을 진행했을 때의 결과로 N개의 수를 뽑는 상황을 생각해보면 아래와 같습니다. 1. N - 1개의 수로 게임했고, 마지막 순서가 상대(B)에게 갈 때 A가 처음 뽑은 수의 약수에 1을 포함한다면 똑같이 마지막 순서가 상대에게 가므로 (A)승리 2. N - 1개의 수로 게임했고, 마지막 순서가 나(A)에게 올 때 A가 처음 순서에 1만 집고 시작하면 마지막 순서가 상대에게 가므로 (A)승리 3. 따라서 N이 1..

문제 https://www.acmicpc.net/problem/17080 17080번: 결함 게임 첫째 줄에 돌의 개수 N이 주어진다. (1 ≤ N ≤ 5,000,000) www.acmicpc.net 문제 풀이 각 플레이어는 턴마다, 만약 현재 보드 위에 있는 돌탑 중 어딘가에 올릴 수 있는 돌이 남아있다면, 반드시 그러한 돌들 중 하나를 골라 올릴 수 있는 돌탑 중 원하는 돌탑 위에 올린다. 만약 어떤 돌탑에도 돌을 올릴 수 없다면, 남아있는 돌 중 아무거나 하나를 골라 보드 위에 새로운 돌탑의 바닥을 만든다. 모든 돌이 소진된 뒤, 돌탑의 개수가 홀수이면 선공이 이기며, 짝수이면 후공이 이긴다. 위 조건들을 생각하며 돌의 개수를 한 개씩 늘려보면 아래의 규칙을 찾을 수 있습니다. 1. k개의 돌을 둬..