99클럽 코테 스터디 10일차 TIL - 병든 나이트 (그리디)

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

접근방식

• 2칸 위로, 1칸 오른쪽
• 1칸 위로, 2칸 오른쪽
• 1칸 아래로, 2칸 오른쪽
• 2칸 아래로, 1칸 오른쪽

총 4가지 방향으로 움직일 수 있는데 모두 오른쪽으로만 움직일 수 있다.
따라서 행과 열의 크기에 따라 나눠서 처리해야 한다.

• N = 1일때 (행이 1개)
  • 행이 1개인 경우 위나 아래로 이동할 수 없으니 1칸만 방문 가능
• N = 2일때 (행이 2개)
  • 1칸 위로, 2칸 오른쪽 또는 1칸 아래로, 2칸 오른쪽 방향으로만 이동 가능
  • 두 방향 모두 오른쪽으로 2칸씩 이동하므로, M칸을 2로 나눈 값(올림)이 방문할 수 있는 최대 칸 수
  • 이동 방법을 모두 사용하지 않을 때 나이트는 최대 4번까지만 이동할 수 있으므로 최대값은 4
• N ≥ 3 이고 M < 7일때
  • 모든 이동 방법을 사용하면 총 6칸 오른쪽으로 이동해서 M ≥ 7이어야 가능하므로 M < 7일 경우 4번 이하로만 이동 가능
  • N ≥ 3 이므로 모든 행 방문 가능
• N ≥ 3 이고 M ≥ 7일때
  • 오른쪽으로 1칸 이동하는 두 가지 방식만 사용할 경우 1 + (m-1) = m칸 방문 가능
  • 4가지 이동 방법을 모두 사용해야 하므로 처음 4번 이동에서는 최소 6칸 오른쪽으로 이동해야 함
  • M-6개의 열에 대해서만 최적의 방법을 사용할 수 있어서, 최대 방문 칸 수는 1 + (m-1-2) = m-2

구현

const fs = require("fs")
const [n, m] = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map(Number)

if (n === 1) console.log(1)
else if (n === 2) console.log(Math.min(4, Math.floor((m + 1) / 2)))
else if (m < 7) console.log(Math.min(4, m))
else console.log(m - 2)

4가지 방법을 모두 사용한 후에는 최적의 선택을 해야되는 점 때문에 그리디로 분류된 것 같다.
케이스 분석이 중요한 문제인 듯...