[백준 1783 : PYTHON] 병든 나이트

문제 풀기 : 1783번

1783번: 병든 나이트

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다.
병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

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

병든 나이트는 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다.
병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다.
이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구한다.

문제풀이

최적의 해를 구하는 그리디 문제이다.
처음 문제을 풀 때 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구하라고 해서 이동한 칸의 개수를 전부 더하는 줄 알았다.
그러나 전부 구하는 것이 아니라 한 번 이동했을 때의 도착지점의 칸 수 1개를 의미하는 것이었다.

 

이동 방법은

이러한 형태로 움직인다.

 

이동 조건을 살펴보면
- 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다.
- 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
즉, 이동횟수 <= 3 일 때, 이동 방법에 제약이 없고
이동횟수 >= 4 일 때부터 이동 방법을 최소 한 번씩을 써야한다.

이동 방법이 모두 오른쪽 방향으로 이동하고 행의 방향이 달라지는 점을 고려하면 행의 크기에 따라 조건을 따져주면 된다.

 

N = 1 일 때는 어떠한 조건도 사용할 수 없으므로 이동이 일어나지 않아 방문한 칸의 수는 1이다.

 

N = 2 일 때 (result는 총 방문한 칸의 수이다.)
M = 1, 2 -> result = 1
M = 3, 4 -> result = 2
M = 5. 6 -> result = 3
M >= 7 -> result = 4

 

M = 1 -> result = 1
M = 2 -> result = 2
M = 3 -> result = 3
M = 4 -> result = 4
M = 5 -> result = 4
M = 6 -> result = 4 : 6일 때는 4가지 이동방법을 사용하지 않았으므로 이동하지 않는다.
M = 7 -> result = 5
M = 8 -> result = 6
M = 9 -> result = 7
.
.
.

전체코드

# 세로(행) : n, 가로(열) : m
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)