[ 𝗕𝗢𝗝 ] 1783번 병든나이트 - 그리디 | JavaScript

🎯 문제 설명

🧩 백준 1783번 - 병든 나이트 | 실버3

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

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

const move = [
	(2, 1), 
	(1, 2), 
	(-1, 2), 
	(-2, 1)
];

따라서, 병든 나이트는 출발 이후로 왼쪽으로는 다시 가지 않습니다.

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

병든 나이트의 이동 횟수가 4번보다 많아서 이동 방법을 모두 한 번씩 사용하려면 체스판의 가로 길이가 적어도 7 이상이어야 합니다.

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

입력

• 체스판의 세로길이 N, 가로길이 M ≤ 2,000,000,000

100 50
1 1
17 5

출력

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

48
1
4

👩🏻‍💻 문제 풀이

1. 방문한 칸을 세기 위해 count 변수를 선언해 줍니다.

   let count = 0;

2. 체스판의 세로 길이(N)이 1이면 세로 이동이 불가능하므로 이동할 수 없습니다. 따라서 병든 나이트는 시작 위치만 방문합니다.

   if(N === 1){
   	count = 1
   }

3. 체스판의 세로 길이(N)이 2이면 1칸 위로, 2칸 오른쪽(1, 2) 혹은 1칸 아래로, 2칸 오른쪽(-1, 2)으로만 이동할 수 있습니다.

   이 때에는 체스판의 가로 길이(M)에 따라 오른쪽으로 갈 수 있는 만큼만 위, 아래로 이동하면서 움직일 수 있습니다. 2칸씩 이동하므로 가로 길이를 2로 나눈 만큼 이동할 수 있습니다.

   문제에 따르면 4번 이상 이동하려면 모든 이동을 다 써야 하므로, 이 경우에는 모든 이동을 다 사용하지 못하니 딱 4번까지만 이동할 수 있습니다.

   if(N === 2) {
   	count = Math.min(4, Math.ceil(M / 2))
   }

4. 문제 설명의 그림을 보면 4가지 방향으로 모두 이동하는 경우, 체스판은 최소 세로 3, 가로 7의 크기가 필요합니다.

   따라서 체스판의 세로 길이(N)이 3 이상인 경우 부터는 가로 길이(M)이 7을 넘는지 안 넘는지에 따라 다릅니다.

   만약 7을 넘지 않는 다면, 4번까지만 이동할 수 있습니다. 이 때 가장 많은 칸을 방문하려면 오른쪽으로 1칸씩만 이동합니다. 즉, 4번 내에 2칸 위로, 1칸 오른쪽(2, 1) 혹은 2칸 아래로, 1칸 오른쪽(-2, 1)으로만 이동합니다.

   7을 넘는 다면 모든 방향을 다 사용한 후 부터 최대한 많은 칸을 방문하기 위해 오른쪽으로는 1칸씩만 이동하게 됩니다. 이를 조금 다르게 말하자면 조건에 따라 (1, 2), (-1, 2)일 때만 가로로 2칸씩 이동하고 그 외에는 무조건 2씩 이동합니다. 따라서 가로 길이(M) - 2 만큼 이동하게 됩니다. (2칸씩 이동하면서 들리지 않은 2칸만 빼줍니다.)

   if(N >= 3) {
   	if(M < 7) {
   		count = Math.min(4, M);
   	} else {
   		// M >= 7
   		count = M - 2;
   	}
   }

이를 정리하면 다음과 같습니다.

체스판 크기	설 명	count
N === 1	세로 이동이 불가능하여 이동하지 못함	1
N === 2	수직으로 한 칸만 이동 가능하므로, 오른쪽으로는 2칸 씩 이동하게 됨 → 따라서 M / 2 < 4	Math.min(4, Math.ceil(M / 2)
N ≥ 3, M < 7	수직 이동은 자유롭지만 가로가 좁아서 모든 이동을 사용할 수 없고, 최대한 많이 방문하기 위해 오른쪽으로 1칸씩만 이동하게 됨 → 따라서 M < 4	Math.min(4, M)
N ≥ 3, M ≥ 7	4가지 방향으로 모든 이동이 가능하고 이후에는 최대한 방문하기 위해 오른쪽으로 1칸씩 이동 → 초기의 2칸 이동하는 경우를 제외하고 가로길이만큼 이동하므로 M - 2	M - 2

최종 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const [N, M] = input.split(' ').map(Number);

let count = 0;

if (N === 1) {
count = 1;
} else if (N === 2) {
count = Math.min(4, Math.ceil(M / 2));
} else if (N >= 3 && M < 7) {
count = Math.min(4, M);
} else {
count = M - 2;
}

console.log(count);