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

🟠 문제

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

1783번: 병든 나이트

 

🟠 나의 풀이

처음에 조금 헤맸다. 실버3인데 ... 왜이러지? 하먼셔 현타가 왔었고,,, 잠깐 힌트를 찾아보니 그냥 규칙을 찾아내면 되네...? 그리디라고 해서 너무 수학적으로 어떻게든 찾아보려고 했다.... 

그림을 그리면서 생각해보니까, N의 길이와 M의 길이에 따라서 최대 갈 수 있는 칸의 수가 정해져있었다. 왜냐면, 4번 이상을 움직이기 위해서는 최소 4개의 방향전환방식을 모두 사용해야했고, 그래서 한두가지의 이동방식을 사용하기 위해서는, 최대 3번까지밖에 못움직이기 때문이다.

1. N=1 인 경우에는 아무데도 움직일수가 없다. 즉, 처음 도착한 그곳이 방문한 칸수이다. 딱 한칸 방문 가능하다.

2. N = 2인 경우에는, 2번과 3번 방향키만 사용할 수 있다. (위아래로 한칸씩만 이동가능하다는 뜻.)
근데 또, 무한대로 움직일 수 없고, 두가지의 방향키만 사용하기 때문에 최대 3번만 움직일 수 있다. 

그림을 이렇게 그렸다. 3번 움직일 수 있지만, 이것도 M이 5이상이어야한다. 그렇다면,, N=2라면, 최대로 갈 수 있는 4칸과 입력받은 M 사이에서 규칙을 찾아야한다. 그 찾은 규칙은 다음과 같다.

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

M이 2라면 움직이는 최대 수는 4밖에 안되고, M이 7보다 작으면 4보다 그 이하의 수를 선택해야하고, M이 7보다 큰 수를 입력받게 되면 아무리 커도 4만 선택할 수 있다. 그래서 최소값을 4와 비교해서 넣어준다.

3. N = 3인경우
이떄는 1번과 4번 방향키를 사용하면 각 열마다 방문할 수 있다. 즉 M만큼 움직일 수 있다. 하지만 여기서도, 1과 4번방향키만 사용하기 때문에 최대 움직일 수 있는 칸수는 4로 정해져있다. 

여기서 조건문을 생각하는데 조금 애를 먹엇다. 일단 다음 조건부터 보고 정리해보자.

4. 모든 방향키를 사용하기 위해서는 M이 무조건 7이상이어야한다.
모든 방향키를 한번씩 사용하기 위해서는, 가로길이가 7이상으로 길어져야한다. 그렇지 않으면, 방향키는 3번이하로 사용할 수 밖에 없고, 지금까지 작성한 위의 조건들에 부합하게 될 것이다. 

만약 M이 7이하이면, 각 열마다 방문하는 방식이 최대일것이다. (1 4 1, 4 1 4 이렇게 방향키를 사용해서 4칸을 방문하는게 최대겠지)
그래서 여기서도 min을 활용해서 3번과 합쳐진 조건을 줄 수 있다. (n==3인 경우도, 결국엔 M<7 인 조건과 같다. 열마다 방문하는 거니까!)

min( 4, M)

 

5. 이 모든 조건을 빗겨나간다면, 어떻게 될까?

결국 네가지의 방향키는 전부 오른쪽 방향을 향하게 되어있다. 모든 방향키를 사용하고, 한가지 방향키만 무한대로 사용해서 무한대로 내려간다고 쳐도, 각 열마다 한칸씩 방문하는 것이다. 결국,, 4가지의 방향키를 모두 사용한 최대칸수 5에다가, M-7열만큼 칸수를 이동할 수 있다. (7을 빼주는 이유는, 7열기준으로 5칸을 이동했기 때문에, 남은 열마다 방문하는 횟수를 더해주는 것이다.)

와,, 생각보다 간단한 문젠데, 이게 설명하고 생각하는데 은근히 애를 먹었던 문제다. 생각만 잘 해놓으면 코드는 진짜 간단한데 말이다.... 이 과정을 생각해내고, 조건문을 간단하게, 그리고 모든 예외사항을 다담을 수 있도록 추려내는게 관건이었다. 어려웠네.. 실버3주제에..! 하..

 

🟠 정답코드

import Foundation

let nm = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nm[0]
let m = nm[1]

private func solution(_ n: Int, _ m: Int) {
    if n == 1 {
        print(1)
    } else if n == 2 {
        print(min(4, (m+1)/2))
    } else if m < 7 {
        print(min(4, m))
    } else {
        print(m-2)
    }
}

solution(n, m)