[Python 알고리즘] 백준 1783번 : 병든 나이트

문제

• 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
  1. 2칸 위로, 1칸 오른쪽
  2. 1칸 위로, 2칸 오른쪽
  3. 1칸 아래로, 2칸 오른쪽
  4. 2칸 아래로, 1칸 오른쪽
  병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
• 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

입력

# Case 1
100 50

# Case 2
1 1

# Case 3
17 5

# Case 4
2 4

# Case 5
20 4

출력

# Case 1
48

# Case 2
1

# Case 3
4

# Case 4
2

# Case 5
4

내가 제출한 풀이 - 미제출

문제 자체를 이해하지 못했다.. 문제 자체가 많이 불친절하고 이해하기 힘든 문제라고 생각이 된다.

정답

import sys

n, m = list(map(int, sys.stdin.readline().strip().split()))
res = 0

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

print(res)

문제풀이

첫 번째로 봐야할 부분은 이 곳이다.

• 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

입력 부분의 조건인데 N과 M은 2,000,000,000보다 작거나 같은 자연수라고 서술한다. 이 말은 즉, 2차원 배열, BF, DP와 같은 알고리즘이 아닌 수학적으로 다가가야 한다는 부분을 뜻하고 있다. 이러한 조건은 이 문제가 그리드 문제야 라고 알려주고 있다. (BF, DP로는 큰 숫자를 시간 제한 2초 안에 풀 수 없음)

if n == 1:
	res = 1

입력 예시를 보면 1 1 입력 시 출력이 1이라고 나오게 된다. 이 말은 즉, 출발지점도 방문할 수 있는 칸 중 하나라고 뜻하고 있는 것이다.

elif n == 2:
    res = (m + 1) // 2
    res = min(res, 4)

(m + 1) // 2

m + 1은 출발 지점도 방문한 칸으로 치기 때문이다.

n이 2이기 때문에 조건을 2, 3번만 충족할 수 있다. 그러면 하나의 패턴이 보이는데 그게 2칸마다 한 번 씩 이동을 한다는 것이다. 그래서 나누기 2를 해주는 것이다.

 

min(res, 4)

이동 횟수는 화살표들을 뜻하는데 위 그림은 총 3번을 이동했다. 만약, 4번이상 이동 시 조건 1, 2, 3, 4를 충족시켜야 하기 때문에 방문할 수 있는 총 칸의 개수는 4개가 최대이다. 그래서 4보다 낮으면 res가 방문한 칸의 개수이고, 4이상이라면 4번이 최대이기 때문에 조건문이 걸려있는 것이다.

elif m < 7:
    res = min(m, 4)

m < 7

조건 1~4를 충족할라면 m은 총 7칸이 필요하다. 그래서 조건문을 7로 잡은 이유가 이것이다. n == 2는 n의 길이를 제한을 뒀다면 m < 7은 m의 길이를 제한 두는 것이다.

 

조건 1, 2, 4 번을 사용한 것이다. m은 7이상이 아니므로 방문할 수 있는 칸은 4개이다.

 

조건 1, 4번을 반복하여 사용한 것이다. 이러한 상황에서 의문점이 2가지 들것이다.

1. 왜 조건 1, 2, 3, 4를 다 쓰지 않고 1, 4만 반복하는 거지?

- 이동 횟수가 4 미만이면 조건을 어떻게 사용해도 상관이 없다고 문제에서 나와있다.

2. 칸이 남는데 왜 멈춘거지?

- 이동 횟수가 4 이상이면 조건 1, 2, 3, 4를 다 써야한다고 문제에서 나와있다.

 

그래서 방문할 수 있는 칸은 최대 4칸이다. 그래서 res = min(m, 4)가 나오는 것이다.

else:
	res = m - 2

m - 2

n > 3이고, m >= 7이면 4번의 조건을 사용 후 1, 4번만 반복해서 이동하면 되기 때문이다.

이동 횟수가 4번 이상이라면 조건 2, 3을 한 번 씩(오른쪽을 총 4칸 이동) 사용 후 이동 1개당 방문한 칸 수가 1씩 증가하기 때문이다. 예를 들어 (2 + 2 + 1 + 1 + 1 + 1 + 1 ... + 1)라면 m에다가 -2를 해 (1 + 1 + 1 + 1 + 1 + 1 + 1 ... + 1) 이러한 형태로 만들어 준 것이다.