[BOJ/Greedy] 백준 1783 - 병든 나이트 (Java)

1783 - 병든 나이트

https://www.acmicpc.net/problem/1783

문제

병든 나이트가 N x M 크기 체스판의 가장 왼쪽아래 칸에 위치
4가지로만 움직일 수 있음
1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 함
이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 함
/ 4번보다 적은 경우(방문한 칸 < 5개): 이동 방법에 대한 제약 X

=> 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수?

입력: 체스판의 세로 길이 N, 가로 길이 M (N, M (자연수) <= 2,000,000,000)
출력: 여행에서 방문할 수 있는 칸의 개수 중 최댓값

---

풀이

• 행 = 가로줄(row) = 세로 인덱스 (x)
• 열 = 세로줄 (column) = 가로 인덱스 (y)

=> `map[x][y]`: x번째 줄의 y번째 칸

 

위로 이동: `x - 1` / 아래로 이동: `x + 1` / 왼쪽 이동: `y - 1` / 오른쪽 이동: `y + 1`

1. 2칸 위로, 1칸 오른쪽: (x - 2, y + 1)
2. 1칸 위로, 2칸 오른쪽: (x - 1, y + 2)
3. 1칸 아래로, 2칸 오른쪽: (x + 1, y + 2)
4. 2칸 아래로, 1칸 오른쪽: (x + 2, y + 1) 

=> 모두 오른쪽(y) 증가, 세로(x)의 변화만 O = 오른쪽으로만 이동 O

 

• `N == 1` => 세로 1칸
  
  • x가 0 -> 위아래 이동 X 
  • 제자리만 방문 => 1
• `N == 2` => 세로 2칸
  • 2, 3번 방식만 가능 -> 2칸 오론쪽 이동, 위/아래 1칸 이동
  • 제한: 최대 4가지 이동방식을 모두 사용해야 4칸 이상 이동 가능
  • 방문 칸 수: `min(4, (M + 1) / 2)`
• `N >= 3` => 세로 3칸 (위/아래 총 3칸 이동)
  • 이동 4가지 모두 사용 -> `M >= 7` (오른쪽으로 총 6칸 이동)
  • 방문 칸 수: `M < 7` -> `min(4, M)` / `M >= 7` -> `M - 2`

---

코드

import java.io.*;
import java.util.*;

// 병든 나이트
public class boj_1783 {
    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 cnt = 0;
        if (N == 1) cnt = 1;
        else if (N == 2) {
            cnt = Math.min(4, (M + 1) / 2);
        } else {
            if (M < 7) {
                cnt = Math.min(4, M);
            } else {
                cnt = M - 2;
            }
        }

        System.out.println(cnt);
    }
}