Algorithm) BOJ) 백준 1783 - 병든 나이트

문제보러가기

1. 초기접근

문제 조건 해석

나이트가 움직일 수 있는 4개의 방식이 주어지는데, 이동 횟수가 4번 이상인 경우에는 각각 한 번 이상은 사용해야 한다.

이 말을 잘 이해해야 한다. 4번 이상까지 이동 방식을 한 번씩 모두 사용했다면 그 다음 부터는 한 가지 방식만 계속 사용해도 된다.

알고리즘

N이 1이라면,

움직일 수 없으므로 현재 자신의 위치인 1이 된다.

 

N이 2라면,

n 은 (3번까지 이동한) 4가 최대이고 이후로는 M이 아무리 커도 4를 넘을 수 없다. n이 2밖에 안되서 오른쪽 두 칸씩 밖에 움직일 수 없으므로

(m+1) / 2 와 4 중에서 작은 수를 고른다.

 

N이 3이상이라면,

4번 이동 전까지 각 방식을 모두 사용하고 그 다음부터 1번과 4번 방법을 번갈아 사용하면서 오른쪽 1칸에 1번씩 이동할 수 있다.

m > 6 칸을 이동하려면 반드시 4번 이상 움직여야 한다.

m <= 6 칸은 최대 4칸까지 움직일 수 있어서 m과 4중에서 작은 것을 고르고,

m > 6 칸 부터는 한 칸씩 움직일 수 있으므로 m-2가 답이다.

 

2. 회고

이동 횟수가 4번 이상인 경우에는 각각 한번 이상 이용해야 된다는 말을 잘못 이해 했었다. 바보같이 처음엔 4번마다 각각 방식을 모두 사용해야 해나 생각을 했다…

처음에는 dfs 방식으로 풀어야 하나 생각을 하기도 했었는데 4회 이동 이상부터는 1번과 4번 이동을 번갈아 쓰기만 하면 되므로 굳이 어렵게 풀 필요가 없다.

역시 문제를 잘 보고 이해하는게 첫번째, 두번째는 한 두개의 경우의 수를 직접 그려보면서 원리를 이해해야 적합한 풀이를 찾을 수 있을듯하다. 아직도 갈 길이 멀다.

 

3. 코드

guard let input = readLine()?.split(separator: " ").map({Int($0)!}) else {fatalError()}
let n = input[0]
let m = input[1]

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