BOJ-1783 병든 나이트 Swift

문제

병든 나이트가 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보다 작거나 같은 자연수이다.

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

내가 푼 풀이

- 체스판에서 나이트가 움직인다면, 위 아래는 자유자재로 움직이지만, 반드시 오른쪽으로 이동이 된다.

- 체스판에서 나이트의 움직임은 최대한 오른쪽으로 적게 가야 많이 움직이게 된다.

- 이는 나이트가 방문하는 칸의 최대가 되려면, 오른쪽으로 최대한 적게 움직여야 한다.

- 나이트의 최적의 움직임은 1번 4번을 반복해서 오른쪽으로 최대한 적게 움직이는 것이다.

- 나이트의 이동 횟수가 4번보다 적지 않다면 위 4가지 모두 한 번씩은 사용해야 한다.

- 이는 체스판의 크기 기준으로 4번 모두 움직일 수 있는 크기의 체스판이 주어진다면, 1번, 2번, 3번, 4번 움직임 모두 소화해 낸다.

- 반대로 크기가 작다면 최고효율의 움직임만 실행한다.

 

- 1번, 2번, 3번, 4번 모두 이동가능한 체스판의 크기는 어느 정도 일까

- 세로이동은 +2 , +1 , -1 , -2이다. 세로의 크기는 3칸 정도 되면 모두 움직일 수 있다.

- 가로이동은 +1 , +2 , +2 , +1이다. 가로의 크기는 7칸 정도 되면 모두 움직일 수 있다.

- 이는 나이트의 시작지점이 주어져있기 때문에, 3X7 크기 이상의 체스판이 주어진다면, 가능한 모든 움직임을 한 번씩 소화시킨다.

	O				O
			O
시작점						O

위와 같이 모든 움직임을 한번씩 소화했을 때의 경우이다.

 

- 세로의 크기가 3보다 작다면

세로의 크기가 1이면 움직일 수 없다.

세로의 크기가 2라면

		O
시작점				O

위와 같이 2번, 3번 이동만 가능하지만, 이동방법을 모두 사용하지 않았으므로 방문가능한 지점은 가로가 아무리 길어도 최대 4가 된다.

 

 

- 가로의 크기가 7보다 작다면

	O		O
시작점		O		O

위와 같이 1번, 4번 이동으로 최대한 많은 지점을 방문했지만, 이동방법을 모두 사용하지 않았으므로 방문가능한 지점은 최대 4가 된다.

 

 

위의 경우바탕으로 코드로 구현해 보자.

import Foundation

var input = readLine()!.split(separator: " ").map{ Int($0)! }
var result = 1
var num = 0
var idx = 1

// 세로의 길이를 기준으로 길이가 1이면 이동 불가능
// 길이가 2이면 2,3번 이동방법 가능
if input[0] == 2 {
    result = (input[1] + 1) / 2
    if result > 4 {
        result = 4
    }
} else if input[0] > 2 {
    // 가로의길이가 7보다 크다면, 모든 이동방법 이용가능
    // 모든 이동방법을 한번씩 사용한 후, 남은 크기를 가장 효율적인 이동인 1번,4번으로만 이동
    if input[1] > 6 {
        result = 5
        idx = 7
        num = input[1] - 7
        result = result + num
    } else {
        // 가로의 길이가 7보다 작아도, 가장 효율적인 이동인 1번,4번을 이용하지만
        // 모든 이동방법을 사용하지 않았으므로 방문지점은 최대4가된다.
        result = result + input[1] - 1
        if result > 4 {
            result = 4
        }
    }
}

print(result)