BOJ 27741 - 견제 미로찾기

BOJ 27741 - 견제 미로찾기

$dp[y][x][k]=$현재 $(y,x)$에 있고 $k$ 값일 때, $N$ 포지션인가? 로 두자.

얼핏보면 $O(N^4)$ 처럼 보이지만, 일단 특정 수의 약수는 $O(\sqrt{N})$으로, 그리 많지 않고, 일단 오른쪽이나 아래쪽으로 많이 가는순간 그 다음 가능한 경우의 수가 급격히 줄어들기 때문에 믿음으로 구현해서 제출하면 된다.

그냥 상남자식으로 구현했는데 왜이리 나혼자 빠르게 나온지 모르겠다.

알고보니 내 코드가 두 가지 최적화가 되어있었다.

• $dp[y][x][k]$ 에서 $k$ 의 약수들에 대해서 검사를 하고 거기서 하나라도 지는 경우가 있다면 이 경우 이긴다고 빠르게 반환하는 코드가 그렇지 않은 코드보다 $10$배 이상 빠르다.
  • 즉, 이동하는걸 검사하는것보다 약수쪽으로 가는걸 검사하는걸 빠르게 해야한다.
  • 이런류의 최적화는 백트랙킹이나 DP에서 종종 쓰인다.
• int 대신 char 로 DP 배열을 선언했다.
  • 상태가 $-1, 0, 1$ 밖에 없는 DP는 char 로 선언하는게 훨씬 좋다.