백준 1783 병든 나이트

문제

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

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

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

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

제한 사항

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

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString();

const sol = (input) => {
  const [row, column] = input.split(" ").reverse().map(Number);

  if (column === 1) {
    return 1;
  } else if (column === 2) {
    return Math.min(4, parseInt((row + 1) / 2));
  } else {
    if (row <= 6) {
      return Math.min(4, m);
    } else {
      return row - 2;
    }
  }
};


console.log(sol(input));

bfs처럼 풀다가 아닌 것 같아서 다른 풀이를 참고했다.

이 문제는 세로의 길이에 영향을 받는다. 그리고 오른쪽으로만 이동이 가능한 것이 포인트이다.

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

세로의 길이가 1일 때,
이동이 불가능 하기 때문에 1 (처음 위치 포함) 출력하면 된다.

세로의 길이가 2일 때,
위, 아래로 한칸 밖에 이동 할 수 없으므로 2,3번 옵션으로만 움직임이 가능하다.
가로의 길이가 충분히 긴 값이라고 가정했을 때, 방문 칸 수가 5개를 넘어가고 부턴 다른 움직임 옵션도 사용해야하는데 그러질 못해서 최대 값은 4가 된다.
가로의 길이에 1을 더하고 2로 나눈 것과 4중 작은 값을 출력하면된다.

세로의 길이가 3이상 일 때 이때부턴 가로의 길이를 봐줘야한다.

가로의 길이가 6이하 일 때, 최대로 움직이려면 오른쪽으로 한칸만 가는 1,4번 움직임을 최대로 해야한다. 가로의 길이가 6이 넘지 않으니 최대값은 마찬가지로 4가된다.
따라서 4와 가로의 길이 중 작은 값을 출력하면 된다.

가로의 길이가 7이상 일 때,
모든 움직임이 가능하다. 모든 움직임을 한번씩 사용해야하는 조건때문에 2,3을 한번씩 쓰고 나머지는 1,4로 움직이면 최대값이다. 따라서 가로의 길이 - 2를 출력하면 된다.