백준 1783. 병든 나이트

https://www.acmicpc.net/problem/1783

1783번: 병든 나이트

 

시간제한만 없더라면 재귀(dfs)로 풀수 있을것 같지만 가로세로 길이 N,M이 최대 20억이므로 택도 없다.

따라서 그리디로 풀어야 하는데 움직일수 있는 방법은 다음과 같다.

 

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

네가지 경우 모두 오른쪽으로는 무조건 이동하게 된다.

따라서 세로의 크기 N은 크게 중요하지 않다. 왜냐하면 위로 이동 아래로 이동을 반복하면 되기 때문이다. 

케이스를 나눠보자면

 

1. 세로(N)이 1인 경우

=> 이 경우는 1~4번 모두 위아래로 한칸 이상은 움직여야 하기 때문에 선택할수 있는 경우가 없기 때문에 움직일수 없다. 

      내가 원래 있던 (0,0) 1칸 이 답이다.

 

2. 세로(N)이 2인 경우 

    이 경우는 가로 (M)이 9이상인 경우와 미만인 경우로 나뉜다.

    세로 크기가 2라면 네가지 경우 중 2,3,번 방법으로만 이동할수 있다. (1,4 는 2칸 위나 아래로 이동해야하므로)

    가로 크기가 9이상이면 2,3번 방법으로 가로끝까지 이동할수 있어보이지만 문제의 조건 중 방문 칸이 5 이상이면 네가지 방법 모두 사용      해서 이동해야 하기 때문에 무조건 4칸만 이동할수 있다.

    가로 크기가 9미만이면 2,3번 방법을 번갈아 사용해서 가로 끝까지 이동한다. 

 

3. 세로(N)3 이상, 가로(M) 5 이하인 경우 

    이 경우는 오른쪽으로 1칸 이동하는 1,4번 방법으로 가로 끝까지 이동하면 된다. 

 

4. 세로(N) 3 이상, 가로(M) 5 이상인 경우

     이때는 1~4번 방법 모두 사용해야 한다. 

     일단 오른쪽으로 최소로 이동하는 1,4번 방법으로 가로 끝까지 이동한다. 

     이때 5칸이상 이라면 4가지 방법 모두 사용해야 하므로, 2칸씩 이동하는 2,3번 방법도 한번씩만 사용하면 된다.

     즉 2칸씩 이동하는 2,3번 방법을 한번씩 더 사용하니까 2칸을 빼주면 된다.