STUDY

경로 게임 문제 현정이는 경로 게임을 하고 있다. 경로 게임은 정사각형 칸으로 이루어져 있는 직사각형 격자판에서 진행된다. 격자판의 행의 개수는 항상 2이며, 열의 개수는 양수이다. 각 칸은 검정색 또는 하얀색으로 칠해져 있다. 격자에서 왼쪽-오른쪽 경로는 시작 칸이 가장 왼쪽 열에 있는 칸이고, 마지막 칸이 가장 오른쪽 열에 있는 경로이다. 이때, 경로 상의 모든 칸은 하얀색이어야 하며, 경로상에서 연속하는 칸은 모두 인접해야 한다. 격자판의 하얀색 칸을 검정색 칸으로 바꾼 경우에도 왼쪽-오른쪽 경로가 존재할 수도 있다. 이때, 왼쪽-오른족 경로가 존재하면서 바꿀 수 있는 하얀색 칸의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 열의 개수 M이 주어진다. (M ≤ 50) 둘째 줄부터 두 개의..

돌 게임 6 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 게임 이론 문제 였긴 때문에 규칙을 찾기로 하였다. 그래서 1, 3, 4개를 선택할 수 있기 때문에 4 까지는 구해보았다. 그랬을 때 SK, CY, SK, SK 가 나왔다 그래서 N=5일 때는 N..

나이트 게임 문제 나이트 게임은 크기가 N×N인 체스판 위에서 진행되는 게임이고, 나이트를 하나씩 턴을 번갈아가며 놓는 게임이다. 나이트는 이미 놓여져 있는 나이트가 공격할 수 있는 칸에 놓을 수 없다. 나이트를 (r, c)에 놓은 경우에는 (r-2, c+1), (r-1, c+2), (r+1, c+2), (r+2, c+1), (r+2, c-1), (r+1, c-2), (r-1, c-2), (r-2, c-1)이 공격할 수 있는 칸이다. 나이트를 놓을 수 있는 칸이 없는 사람이 게임을 지게 된다. 구사과와 큐브러버가 이 게임을 최적의 방법으로 플레이했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 구사과가 먼저 시작한다. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100)가 주어진다..

나무 탈출 문제 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다. '나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다. 이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나씩 놓여있는 채로 시작한다. 어떤 사람의 차례가 오면, 그 사..