[python] 백준 1783 병든 나이트

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

1783번: 병든 나이트

 

문제 해결

• bfs로 풀면 끝이라고 생각했지만 시간초과가 났다.
• bfs, dfs로 시간초과가 나면 결국 dp를 이용해야한다고 생각했다.
• 어느 방향으로 움직이던 오른쪽으로 이동을 해야한다.
• 열이나 행이 1칸이면 무조건 움직일 수 없기 때문에 답은 1
• 행이 두칸이면 열을 2칸 움직여야하기 때문에 열이 최소 3열 이상 있어야 움직인다.
• 4번 이상 움직이려면 움직일 수 있는 방법으로 한번씩 움직여야 한다. (-2,1),(2,1),(1,2),(-1,2) =>total (0,6) 움직임. 그러면 열은 최소 7열이고 행은 3행 이상이다. 아니면 3번 이하이다.
• 즉 열이 6열 이하이면 열을 한칸씩 움직이는 방법((-2,1),(2,1) 반복)으로 움직이므로 m-1번 움직이면 m-1열 움직이게 되어 0열에서 m-1열로 이동하게 된다. 즉 답은 min(3+1,(m-1)+1)이다.
• 열이 7열 이상이고 행이 3행 이상이면 방법 가지수 다 움직인 후 (2,1), (-2,1) 움직이는 것을 반복하면 된다. 답은 m-2

 

CODE

n, m = map(int, input().split())

if min(n,m)==1:
    print(1)
elif n ==2:
    print(min(4,(max(n,m)-1)//2+1))
else:
    if m<=6:
        print(min(4,m))
    else:
        print(m-2)