백준: 1783 병든 나이트

문제

1783번: 병든 나이트

 

문제 풀이

 병든 나이트가 N, M 크기의 체스판을 이동할 때, 방문할 수 있는 칸의 개수의 최대 값을 반환하는 문제이다. 문제를 처음 접하였을 때는 BFS로 푸는 건가? 하고 생각을 했다. 하지만 N, M은 2,000,000,000까지 이므로 최대 값이 입력된다면 시간 내에 통과할 수 없게 된다. 문제를 풀기 위해서 병든 나이트의 이동에 대해 생각해보면, 좌측으로 가지 않고 반드시 우측으로 이동한다는 특징을 가지고 있다. 또한 방문한 칸이 5개 미만인 경우에는 이동 방법에 대한 제약이 없다는 특징을 가지고 있다.

 

 위의 특징을 가지고 경우의 수를 나누어 본다면 다음과 같다.

• N = 1
  • 방문할 수 있는 칸 : 1
  • 병든 나이트가 이동할 수 있는 4가지 방법 중 이동할 수 있는 경우가 없다.
• N = 2
  • M = 1, 2
    • 방문할 수 있는 칸 : 1
  • M = 3, 4
    • 방문할 수 있는 칸 : 2
  • M = 5, 6
    • 방문할 수 있는 칸 : 3
  • M = 7, 8 
    • 방문할 수 있는 칸 : 4
  • M = 9
    • 방문할 수 있는 칸 : 4
  • M = 10
    • 방문할 수 있는 칸 : 4
  • M에 따라 최대 4칸을 방문할 수 있다.
• N = 3
  • M = 1
    • 방문할 수 있는 칸 : 1
  • M = 2
    • 방문할 수 있는 칸 : 2
  • M = 3
    • 방문할 수 있는 칸 : 3
  • M = 4
    • 방문할 수 있는 칸 : 4
  • M = 5
    • 방문할 수 있는 칸 : 4
  • M = 6
    • 방문할 수 있는 칸 : 4
  • M = 7
    • 방문할 수 있는 칸 : 5
  • M = 8
    • 방문할 수 있는 칸 : 6
  • M이 7보다 크게 되면 M - 7 + 5라는 규칙을 찾을 수 있다.

 이와 같은 조건을 정리하여 코드로 작성하면 답을 찾을 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    n, m = map(int, stdin.readline().split())

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