[백준] 1783번: 병든 나이트

1783번: 병든 나이트

 

 

 

이 문제는 그리디 문제인데, 왜 그리디 문제인지 잘 모르겠다는 사람도 있을 것 같습니다.

 

이런 유형의 그리디 문제의 해법은 가능한 경우의 수를 제한을 줘서 따질 수 있다는 것입니다.

 

일단 이동할 수 있는 방식이 (+2, +1), (+2, -1), (+1, +2), (+1, -2) 이렇게 4개로 제한되어 있고, 이동 횟수가 4가 넘어가게 될 때는 이 4가지 방식이 모두 사용되어야 합니다.

 

그림을 그려가며 생각하면 더 쉽게 이해할 수 있습니다.

 

1 x 1 칸이 있을 때라면 답은 1이다.

1 x n 칸이 있더라도 답은 1이다.

이런 식으로 생각하게 되면 생각보다 쉽게 풀 수 있는 문제 중 하나이다.

 

저는 height와 width로 나눠서 생각을 해 보았습니다.

height가 1일 때, 2일 때, 3 이상일 때.

이렇게 3가지 경우로 나눠볼 수 있을 것 같습니다.

 

 

height가 1일 때 > width가 어떻게 변하더라도 처음 위치에서 움직일 수가 없습니다.

 

height가 2일 때 > width의 크기에 따라 (+2, +1), (+2, -1)을 번갈아가며 사용할 수 있습니다. 하지만 4번 이동할 경우부터는 모든 방식을 다 이용해야하므로 만족하지 못합니다. 

이 경우 나이트가 움직일 수 있었던 width의 index는 1, 3, 5, 7 입니다.  

min(4, (width + 1) / 2)

 

height가 3 이상일 때 > 3 이상일 때부터는 width에 따라 4가지 방법 모두를 이용해 이동할 수 있습니다.

3 이상일 경우에도 width가 7 이상일 때와 7보다 작을 때로 나눌 수 있습니다.

 

width가 7 이상일 때 > 이 때는 4번 이동하는 동안 4가지 이동 방법을 모두 이용할 수 있습니다.

그 이후로는 (+1, +2), (+1, -2)를 번갈아 사용할 경우에 가장 많은 곳을 방문할 수 있습니다.

width - 2

 

width가 7보다 작을 때 > 이 때는 4가지 방법을 다 이용할 수는 없습니다.

(+1, +2), (+1, -2)를 번갈아가는 방법으로 계산해야 가장 많은 곳을 방문할 수 있는데, 이렇게 될 경우 도출되는 식은 다음과 같습니다.

min(4, width)

 

 

이렇게 경우의 수를 나눠서 계산을 하면 원하는 답을 구할 수 있습니다.

 

 

#include <iostream>
#include <algorithm>
using namespace std;

int height, width;

void input() {
  cin >> height >> width;
}

int solve() {
  if (height == 1) return 1;
  else if (height == 2) return min(4, (width + 1) / 2);
  else {
    if (width >= 7) return width - 2;
    else return min(4, width);
  }
}

void printAnswer(int ans) {
  cout << ans << '\n';
}

int main() {

  input();
  int ans = solve();
  printAnswer(ans);

  return 0;
}