한국정보올림피아드 썸네일형 리스트형 [DP] 백준 28218 격자 게임 어떤 알고리즘으로 문제를 풀어야 할까? 문제의 크기는 300 * 300에, 말의 위치가 다시 원위치로 돌아가는 방법이 없다. 문제를 하위 문제로 나누어 풀어도 문제가 없다는 이야기. 즉, dynamic programming이 가능한 문제라는 뜻이다. 점화식을 어떻게 수립해야 할까? $$ dp[x][y][turn] $$ (x, y)의 위치에서 현재 turn(한국 or 정올)의 차례일 때 이기는 사람의 번호로 점화식을 정의할 수 있다. 그렇다면, 최선을 다한다는 것은 어떻게 표현할까? 현재 첫번째 한국이가 이길 때를 0으로 표시하고, 두번째 정올이가 이길 때를 1로 설정한다. 그리고, 첫번째 한국이의 turn일 때는 정올이가 이긴다고(=1) 초기값을 설정하고 가능한 케이스에서 최소값(=0, 한국이가 이기는 .. 더보기 이전 1 다음