그리디: 백준 1783 병든 나이트 파이썬

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

1783번: 병든 나이트

풀이:

나이트 문제라고 해서 DFS/BFS로 풀려고 하면 메모리 초과 오류가 발생한다.

체스판의 범위가 2,000,000,000 보다 작거나 같은 자연수이기 때문.

 

N과 M의 값에 따라 나이트가 이동할 수 있는 경우의 수가 정해진다.

 

N = 1

M이 몇이든 관계없이 이동할 수 없다. => 방문할 수 있는 최대 칸은 1

 

N = 2

M = 3일 때 최대 칸은 2, M = 5일 때 최대 칸은 3, 7일 때 최대 칸은 4이다.

그 뒤에 M이 아무리 커지더라도 최대 칸은 4를 넘을 수 없다. 

"병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다."

위 조건 때문에 이동 횟수 3번 까지는 이동 방법을 마음대로 사용해도 되지만, 4번 이상부터는 한 번이라도 더 이동하려면 모든 이동 방법을 사용해야 한다.

 

이 조건을 코드로 나타내면 다음과 같다. 

if N == 2 :
      knight = Math.min(4, (M + 1) / 2);

 

N = 3

N이 3일 경우 체스가 움직이는 방법엔 위와 같이 2가지 경우가 있다.

여기서 주의할 점은 N = 2일 때와 같이 N =3에서도 M이 7보다 작으면 최대 칸은 4칸이라는 점이다.

위 그림은 M이 7 이상일 경우에 해당한다는 것을 알아두자. 

 

적은 횟수에 가장 많은 칸을 방문하기 위해서는 1, 4번 만을 사용하는 것이 방법이지만, 이동 횟수가 4 이상이라면 모든 이동 방법을 한 번씩은 사용해야 하기 때문에 2칸 손해를 봐야 한다. 그 이후엔 1, 4번 만을

사용해 이동하면 된다. 그러므로 M이 7 이상이면 손해 본 2칸을 빼준 M-2칸이 최대 칸이 된다.

 

정답:

N, M = map(int, input().split())
if N == 1:
    scount = 1
elif N == 2:
    scount = min(4, (M-1)//2 + 1)
elif M < 7:
    scount = min(4, M)
else:
    scount = (2 + (M-5)) + 1
print(scount)