CEO

문제 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 병든 나이트가 N, M 크기의 체스판을 이동할 때, 방문할 수 있는 칸의 개수의 최대 값을 반환하는 문제이다. 문제를 처음 접하였을 때는 BFS로 푸는 건가? 하고 생각을 했다. 하지만 N, M은 2,000,000,000까지 이므로 최대 값이 입력된다면 시간 내에 통과할 수 없게 된다. 문제를 풀기 위해서 병든 나이트의 이동에 대해 생각해보면, 좌측으로 가지 않고 반드시 우측으로 이동한다는 특징을 가지고 있다. 또한 방문한 칸이 5개 미만인 경우에는 이동 방법에 대한 제약이 없다는 특징을 가지고 있다. 위의 특..