Baekjoon 1783번 병든 나이트

문제

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

풀이

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

let [n, m] = input().split(' ').map(Number);

let ans = 0;

if(n === 1 || m === 1){
  ans += 1;
}
else if(n === 2){
  m = Math.min(m, 8);
  ans = 1 + Math.floor((m-1)/2);
}
else{
  if(m <= 4){
    ans = m;
  }
  else{
    if(m < 8){
      if(m-1 >= 6){
        ans += 5;
      }
      else{
        ans += 4;
      }
    }
    else{
      ans += 4;
      ans += 2;
      ans += m-8;
    }
  }
}

console.log(ans);

높이가 3 이상일 때 병든 나이트는 4가지 이동 방법을 모두 사용할 수 있다. 이동횟수가 4이상일 경우 이동 방법을 모두 한번이상 사용해야하는 조건을 고려한 모든 경우를 찾아내지 못해 반례를 찾는데 시간이 오래 걸렸다.

높이가 3 이상인 경우는 이동 방법 1, 4 를 반복하는것이 제일 많은 칸을 방문할 수 있다 는 것에만 초점을 맞추다보니 모든 경우를

1. 이동횟수가 4미만일 경우는 무조건 1, 4를 세번 반복하여 총 4칸을 방문
2. 4이상일 경우는 2, 3 을 한번씩 반복할 수 없으면 총 4칸 방문 (반복 가능할 때의 처리의 설명은 생략)

으로 처리하였다.

그림의 파란색 경우처럼 이동방법 2, 3 를 이용해 한번씩 이동하여 조건을 만족시켜준 후 1, 4를 여러번 반복하면 더 많은 칸을 방문할 수 있다.