[백준 1783번] 병든 나이트 (java)

1783번: 병든 나이트

 

막상 문제를 풀고 나니 허무할 정도로 간단한데, 규칙을 찾는데까지 너무 오랜 시간이 걸렸다..

이 문제는 케이스를 나누어서 각 케이스 별로 방문한 칸을 구하는 것이 중요하다.

 

먼저, 나이트가 이동할 수 있는 위치는 다음과 같다.

문제에서 조건이 주어지는데, 4번 이상 움직일 때는 4가지 방법으로 모두 움직여야 하지만,

3번까지 움직일 때는 4가지 방법을 모두 사용하여 움직일 필요가 없다는 점이다. 3번 이동할 때까지는 똑같은 방법으로만 움질이는 것도 가능하다.

 

 

나이트가 아예 움직일수 없는 경우 ( N = 1 || M = 1 )

나이트가 아예 움직일 수 없는 경우는 N이 1이거나 혹은, M이 1인 경우이다.

이 경우에는 나이트가 움직이지 못하므로 나이트가 총 방문한 칸은 처음의 시작 위치뿐이므로 1칸이 된다.

 

나이트가 4가지 방법을 모두 이용하는 경우 ( N >=3 && M>=7 )

- N은 3보다 크거나 같으면 4가지 방법을 모두 사용하여 이동이 가능하다.- M은 7보다 크거나 같을 때부터 4가지 방법을 모두 사용하여 이동이 가능하다.

 

즉, 4가지 방법을 모두 이용했을 때의 최소 N과 M은 3과 7이 된다.

  

위 조건을 만족한다고 했을 때, 나이트가 최대한 많은 칸을 방문하기 위해서는 4가지 방법을 모두 사용하여 이동한 후에는 무조건 ①,④번 방법으로만 이동해야한다. 왜냐하면 ②,③번 방법은 오른쪽으로 두 칸씩 이동하기 때문에 방문 횟수가 ①,④번에 비해 적기 때문이다.

전체 M칸 중에서 4가지 방법으로 이동하고 나면 오른쪽으로는 총 6칸을 이동하게 된다. 그리고 이때까지 방문한 칸은 시작 위치를 포함해서 총 5칸이다.

그리고 나서 이동할 수 있는 남은 칸은 M-7 칸이다. 이때부터는 오른쪽으로 한칸씩만 이동하는 ①,④번 방법으로만 움직일 것이기 때문에 최대 M-7 칸을 방문할 수 있다.

-> 그러므로 N>=3 && M>=7 일 때, 나이트가 방문가능한 최대 칸은 M-7+5 = M-2 칸이 된다.

 

 

N<3 인 경우

만약 N<3인 경우에는 나이트가 최대 몇 칸을 방문할 수 있을까?

우선 이 경우에는 N이 3보다 작기 때문에 4가지 방법을 모두 사용하여 이동하는 것이 불가능하다.

N이 3보다 작으므로 ②,③번 방법으로만 이동할 수 있다.

그러므로 M이 아무리 커도, 나이트가 최대로 이동할 수 있는 횟수는 3번뿐이다. 

 

시작 위치의 열을 제외한 M-1 열 중에서,  ②,③번 방법으로 이동하기 때문에 오른쪽으로 두칸씩 이동하므로 2로 나눈 결과가 나이트가 방문한 칸의 개수가 된다. -> (M-1)/2

(M-1)/2 와 3을 비교하여서 더 작은 값을 나이트가 방문한 총 칸의 개수로 한다.

(모든 방법을 이용하지 않고서는 최대 3번만 움직일 수 있기 때문에)

그리고 처음 시작 위치도 포함시켜야 하므로 1을 더해준다.

1 + Math.min(3, (M-1)/2)

 

 

N>=3 && M<7 인 경우

N이 3보다 크거나 같지만 M이 7보다 작기 때문에 4가지 방법을 모두 이용할 수 없다. 이 때, 방문한 칸 수가 최대가 되기 위해서는 나이트가 오른쪽으로 한칸씩만 움직일 때인 ①,④번 방법으로만 이동할 때이다.

나이트가 오른쪽으로는 한 칸씩만 이동하므로 시작 위치의 열을 제외한 M-1개의 열을 모두 방문하게 되므로 총 방문한 칸 수는 M-1 이 된다.

M-1 와 3을 비교하여서 더 작은 값을 나이트가 방문한 총 칸의 개수로 한다.

(모든 방법을 이용하지 않고서는 최대 3번만 움직일 수 있기 때문에)

그리고 처음 시작 위치도 포함시켜야 하므로 1을 더해준다.

1 + Math.min(3, M-1)

 

 

소스코드 :