백준(1783) - 병든 나이트 Python

백준(1783) - 병든 나이트

문제풀이 : 그리디 알고리즘, 파이썬

해결방법

경우의 수를 생각해봐야만 풀 수 있는 문제다.

처음에는 그래프를 그리고, 가능한 x축과 y축 이동방향 대로 움직이는 모든 경우의 수를 직접 움직이는 bfs 로 풀려고 했지만 정답판정을 받지 못햇다.

1. 행이 1인 경우에는 위나 아래로 움직일 수 없기때문에 현재 자기위치에서 움직이지 못하기때문에 1을 출력한다.

2. 행이 2인 경우에는 위로한칸 후 오른쪽으로 두칸, 아래로한칸 이동후 오른쪽으로 두칸의 경우밖에 이동할 수 없다. 따라서 열의 크기에 따라서 몇번 이동하는지 좌우된다.

하지만 문제에서 이동횟수가 4보다 클 경우 주어진 이동방법을 모두 이동해야 한다고 했으므로 최대 4번을 넘을 수 없기때문에 min(4, (m+1)//2) 를 출력해준다.

1. 열이 6인 경우가 가장 생각하기 까다로웠다.

   오른쪽으로 이동하면서 이동횟수가 4를 넘지 않거나 모든 방향을 다 이동했을 경우의 수가 m이 6인 경우이므로 열이 6보다 작거나 같을 경우엔 min(4,m)를 출력해준다.

2. 그 외에는 4가지 방법을 모두 사용해야하므로 오른쪽으로 두칸 이동해야하는 방법 2번일 때 생략되는 2번만 입력받은 열에서 빼준 값을 출력하면 된다.

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

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