백준 - 병든 나이트(Swift)

백준 - 병든 나이트(Swift)

 

 

 문제 설명

 

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

1783번: 병든 나이트

 

 나의 풀이

 

문제에서 n과 m의 범위가 2억까지인 것을 보고, 이동방법이 4가지 이상인 경우는 한번 이상씩 사용해야한다는 것을 보고 조건별로 풀어야 한다는 것을 직감했다.

 

즉 4가지 이하의 경우와 4가지 이상의 경우를 따져봐야한다.

 

일단 N이 1일때(행이 1)는 위나 아래로 갈 수 없기 때문에 처음위치인 1칸이 최대값이다.

 

N이 2일때는 위로한칸 오른쪽으로 두칸과 아래로한칸 오른쪽으로 두칸밖에 할 수없다. 그렇기에 4가지 이상인 경우는 한 번 이상씩 사용해야한다는 조건을 만족시키기 못하기 때문에 최대로 많이 칠한 개수는 3번이동한 결과인 4칸일 수 밖에 없다. (m+1)/2가 나온 이유는 오른쪽으로 두칸씩 이동할수밖에 없기 때문이다. 

 

N이 3이상일때는 M이 6보다 작거나 같은경우와 큰 경우를 나눠서 따져봐야한다. 

먼저 M이 7일때 딱 4가지이동경로를 만족시킨 상태가 된다. (총 오른쪽으로 6번가기때문). 그리고 전부 사용했으니 가장 많은 곳을 들리기 위해서는 위로두칸 오른쪽으로 한칸과 아래로두칸 오른쪽으로 한칸을 반복하면 되기 때문에 계속 +1씩하면된다. 그래서 M-2가 되는데 여기서 -2가 되는 이유는 4가지 이동경로를 경우의수에 넣을때 위로한칸 오른쪽으로 두칸, 아래로한칸 오른쪽으로 두칸 때문에 이 두 가지 경우에서 각각 한칸씩 빼는 것이다. 

 

그리고 M이 6보다 작거나 같은경우에는 4가지 이동경로를 다 만족시키는 경우가 없기 때문에 3가지 이동경로를 만족시킨 상태인 4개의 체스판에 도달한 게 최대값이 된다. 그리고 m과 함께 최소값을 구하면 되는데 m자체를 넣은 이유는 위로 두칸 오른쪽으로 한칸, 아래로두칸 오른쪽으로 한칸이 최대값이기 때문이다. 

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let n = input[0], m = input[1]

if n == 1 {
    print("1")
} else if n == 2 {
    print(min(4, (m+1)/2))
} else {
    if m > 6 {
        print(m-2)
    } else {
        print(min(4, m))
    }
}