🏇 백준 1783번 - 병든 나이트

🔗 병든 나이트

---

📌 문제 설명

체스판의 크기가 N x M일 때, 병든 나이트는 일반 나이트처럼 이동할 수 없고, 아래의 4가지 방식으로만 움직일 수 있다:

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

나이트는 가장 많이 방문할 수 있는 칸의 수를 구해야 한다.
(현재 서 있는 칸도 방문한 것으로 친다.)

---

🎯 입력 조건

• 첫째 줄에 두 정수 N, M이 주어진다.
  (1 ≤ N ≤ 20,000, 1 ≤ M ≤ 20,000)

---

🔑 핵심 아이디어

이 문제는 이동 방향이 오른쪽으로만 고정되어 있기 때문에,
실제로는 세로(N)의 크기에 따라 경우를 나눠서 그리디하게 접근해야 한다.

---

🧠 풀이 전략

✅ Case 1: N == 1

• 세로로 움직일 수 없으므로 이동이 불가능
• 방문할 수 있는 칸은 단 하나

정답: 1

✅ Case 2: N == 2

• 위아래로 2칸씩 이동하는 (1), (4) 방향은 불가능
• (2), (3) 방향만 가능하므로 → 오른쪽으로만 2칸씩 이동
• 같은 패턴 반복이 제한되므로 → 최대 4번까지만 가능

정답: min(4, (M + 1) / 2)

✅ Case 3: N >= 3

• 모든 방향 사용 가능
• 근데 (2), (3)번 이동을 모두 사용하려면 가로로 최소 7칸 이상 필요
• 그 전까지는 4번 이상 못 움직임
• M이 7보다 작을 경우 → 최대 4칸
• M이 7 이상인 경우 → (M - 2)칸까지 방문 가능

정답:
- if M < 7 → min(4, M)
- else     → M - 2

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int result = 0;

        if (N == 1) {
            result = 1;
        } else if (N == 2) {
            result = Math.min(4, (M + 1) / 2);
        } else {
            if (M < 7) {
                result = Math.min(4, M);
            } else {
                result = M - 2;
            }
        }

        System.out.println(result);
    }
}

✨ 느낀 점

• 그리디 문제지만 조건 분기만 잘 나누면 어렵지 않다.
• 체스판 문제에서 이동 제한이 있는 경우는 “조건 분기”가 핵심!
• 실전 테스트에서 조건 나누기 감각을 기르기 좋다.