[Algorithm] ♞백준 1783 병든 나이트

0. 문제

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

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

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

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

출력
병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

1. 아이디어

💡 하나씩 규칙을 구함
💡 n = 1이면 움직이지 못해 1
💡 n = 2이면, (m+1)/2 만큼 움직일 수 있지만 2가지 방법만을 사용해 최대값이 4임
💡 n ≥ 3이고 n<7이면 m만큼 움직일 수 있지만 4가지 방법을 모두 사용하지 못해 최대값이 4임
💡 n ≥ 3이고 n<7이면 m-2만큼 움직일 수 있음
(처음에 (1칸 위로, 2칸 오른쪽), (1칸 아래로, 2칸 오른쪽) 이 방식으로 움직이고 이후부터는 계속 나머지 2방법으로 반복하면 column 수 만큼 이동한 칸 수가 나옴)

2. 핵심 풀이

1. n = 1이면 움직이지 못해 1

if(n == 1) ret = 1;

1. n = 2이면, (m+1)/2 만큼 움직일 수 있지만 2가지 방법만을 사용해 최대값이 4임

else if(n == 2) ret = Math.min(4, (m+1)/2);

1. n ≥ 3이고 n<7이면 m만큼 움직일 수 있지만 4가지 방법을 모두 사용하지 못해 최대값이 4임

else ret = m - 2;

1. n ≥ 3이고 n<7이면 m-2만큼 움직일 수 있음

if(m < 7) ret = Math.min(4, m);

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_1783 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		int n = Integer.parseInt(s[0]);
		int m = Integer.parseInt(s[1]);
		int ret = -1;
		
		if(n == 1) ret = 1;
		else if(n == 2) ret = Math.min(4, (m+1)/2);
		else {
			if(m < 7) ret = Math.min(4, m);
			else ret = m - 2;
		}
		
		System.out.println(ret);
	}

}

4. 결과

성공✨