[백준/Python] 병든 나이트

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

1783번: 병든 나이트

이 문제는 그리디 문제이다. 해결방법은 다음과 같다.

 

[ 이동 방법 ]

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

1. N == 1 인 경우

- 위 아래로 움직일 수 없으므로 시작칸만 방문할 수 있다. 따라서 방문할 수 있는 칸의 수는 1이다.

 

2. N == 2 인 경우

- 위 아래로 1칸만 움직일 수 있으므로  2, 3번 방법만으로 움직일 수 있다. 가로가 아무리 길더라도 최대 3번 이상 움직일 수 없다. (4번 이상 움직일 경우 모든 방법을 1번 이상 사용해야하기 때문!) 이동횟수는 3과 (M-1)//2 중 작은 값이 된다. 따라서 방문할 수 있는 칸 수 = 이동 횟수 + 1 이므로 4와 (M-1)//2 중 작은 값이 된다. (이동횟수 + 1인 이유는 "이동 횟수 = 이동하여 방문할 수 있는 칸수" 이고 1은 시작칸을 포함한 것이다.)

 

3. N >= 3, M <= 6 인 경우

- N >= 3이기 때문에 세로로는 자유롭게 움직일 수 있다. 하지만 최대로 이동하기 위해서는 오른쪽으로 1칸씩 이동해야 하며 최대 3번 이상 움직일 수 없다. (4번 이상 움직일 경우 모든 방법을 1번 이상 사용해야하기 때문!) 이동횟수는 3과 M-1 중 작은 값이 된다. 따라서 방문할 수 있는 칸 수는 4와 M 중 작은 값이 된다.

 

4. N >= 3, M >= 7인 경우

- 세로와 가로로 모두 자유롭게 움직일 수 있다. 최대로 이동하기 위해서는 오른쪽으로 1칸씩 이동해야 한다. 하지만 모든 방법을 1번 이상 사용해야 하므로 2, 3번 방법을 1번씩 사용하여 2번 이동하게 된다. 이동횟수는 2(2,3번 이동 횟수) + M-5(시작칸과 2,3번으로 이동한 4칸을 뺌) 이다. 따라서 방문할 수 있는 칸 수는 2 + (M-5) + 1 = M - 2 이다.

 

코드는 다음과 같이 작성할 수 있다.

N, M = map(int, input().split())

if N == 1:
    print(1)
elif N == 2:
    print(min(4, (M-1)//2+1))
elif M <= 6:
    print(min(4, M))
else:
    print(M-2)