[백준/JAVA] BOJ 1783- 병든 나이트

👀 문제

1783번: 병든 나이트 ✨ 실버 3

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

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

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

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

예제 입력

100 50

예제 출력

48

🔑 키포인트

구현 그리디 알고리즘 많은 조건 분기

✍️ 코드

생각해 내는 게 너무 어려웠던 문제
설명을 엄청나게 듣고 간신히 풀었다.........

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

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

		n = Integer.parseInt(st.nextToken()); // 세로
		m = Integer.parseInt(st.nextToken()); // 가로

		x = n - 1;
		y = 0;
		cnt = 1;
		
		if (n <= 2) { // 세로가 2보다 작으면
			// 2, 3번만 사용 가능
			while (true) {
				// 2번
				if (move(1) == false) {
					break;
				}
				// 3번
				if (move(2) == false) {
					break;
				}
			}
			System.out.println(cnt);
		} else { // 세로가 2보다 크면 (3 이상)
        	// 만약 가로 크기가 6 이하면
			// 1, 4만 사용하는 것이 최대
			if (m <= 6) {
				while (true) {
					// 1번
					if (move(0) == false) {
						break;
					}
					// 4번
					if (move(3) == false) {
						break;
					}
				}
				System.out.println(cnt);
			} else {
				// 무조건 1, 2, 3, 4 한 번씩 사용해야 함 (4번 이상 이동할 수 있으므로)
				// 2번, 3번 먼저 한 번씩 사용
				move2(1);
				move2(2);
				
				while (true) {
					// 1번
					if (move2(0) == false) {
						break;
					}
					// 4번
					if (move2(3) == false) {
						break;
					}
				}
				System.out.println(cnt);
			}
			
		}
	}
	
    // 나이트를 이동하는 함수
	public static boolean move(int idx) {
		int[] dx = { -2, -1, 1, 2 };
		int[] dy = { 1, 2, 2, 1 };
		
		int nx = x + dx[idx];
		int ny = y + dy[idx];
		
		if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
			x = x + dx[idx];
			y = y + dy[idx];
			cnt += 1;
			
			if (cnt == 4) {
				return false;
			}
		} else {
			return false;
		}
		
		return true;
	}
	
    // 4번 이상 움직일 때 사용할 함수
	public static boolean move2(int idx) {
		int[] dx = { -2, -1, 1, 2 };
		int[] dy = { 1, 2, 2, 1 };
		
		int nx = x + dx[idx];
		int ny = y + dy[idx];
		
		if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
			x = x + dx[idx];
			y = y + dy[idx];
			cnt += 1;
		} else {
			return false;
		}
		
		return true;
	}
}