A. Donut Shops 도넛을 낱개로 파는 첫번째 가게, 도넛을 묶음으로 파는 두번째 가게가 있다. 첫번째 가게의 도넛의 가격 a, 묶음으로 파는 두번째 가게의 도넛의 가격 b개당 c 가 주어질 때 도넛을 최소 x개 사야할 때 첫번째 가게가 이득일 수 있는 x, 두번째 가게가 이득일 수 있는 x를 찾아 출력하는 문제였다. 간단하지만 시간이 좀 걸렸던 발상 + 수학문제이다. 우선 첫번째 가게가 이득일 수 있는 최고의 경우는 1개만 사도될 때 일 것이다. 따라서 a c 라면 b개를 샀을 때 두번째 가게가 이득이 될..
A. Matrix Game (1100) n x m 크기의 행렬이 주어졌을 때 각 칸마다 0은 unclaimed, 1은 claimed 칸을 나타내며 unclaimed 한 칸을 claimed 하기 위해서는 그 칸의 행과 열에 claimed 칸이 존재하지 않아야한다. 이 때 Ashish와 Vivek이 Ashish가 먼저 claim을 시작 할 때 어떤 칸도 claimed 할 수 없게 되었을 경우 패배한다. 두 플레이어가 최적의 선택을 번갈아가며 했을 때 누가 승리하는지 출력하는 문제였다. A번부터 게임이론이 나왔다. 우선 쉽게 관찰할 수 있는 부분은 claim 가능한 칸의 갯수가 홀수면 Ashish가 승리하며 짝수면 Vivek이 승리한다는 것. 따라서 우리는 모든 칸에 대해 그 칸의 행과 열 중 1이 존재하는지..