백준 1783번: 병든 나이트 (Kotlin)

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

1783번: 병든 나이트

 

풀이

문제가 이해하기 어려웠어서 지문을 조금 풀어 써보면 다음과 같다.

 

"이동 방식을 모두 한 번씩 사용해서 움직일 수 있도록 체스판이 주어졌다면, 최소한 모든 방법을 1번 씩은 사용해야 한다. 만약 모든 방식을 사용할 수 없다면, 4번 이상 움직일 수 있더라도 3번 이하로 움직인다.

방법 하나를 사용할 때마다 한 번 움직인 것이며, 시작 지점도 방문한 것으로 간주한다. 위의 조건을 만족하는 최대 방문 횟수를 구하여라."

 

이동 방식을 모두 사용할 수 있는 경우와 없는 경우는 어떻게 나눌 수 있을까?

 

1. 모두 사용할 수는 없는 경우

1) 세로 길이 == 1

이동 방식을 살펴보면 가장 왼쪽 아래에서 시작해서 오른쪽으로만 이동하며, 위나 아래로 함께 움직여야 한다.

따라서 세로 길이가 1이면 가로가 아무리 길어도 움직일 수 없다.

=> 최대 방문 횟수 = 0

 

2) 세로 길이 == 2

 

위 아래로 두 칸씩 올라가는 방법이 있기 때문에,세로 길이가 2이면 위나 아래로 두 칸 이동하는 방법은 사용할 수 없다. => 최대 방문 횟수 = min(4, (세로 길이 + 1) / 2)

 

3) 세로 >= 3 && 가로 < 7

M &lt; 7

세로가 3이상이더라도 모든 방법을 사용할 수 있는 건 아니다. 모든 방법을 한 번씩 사용하면 항상 가로 방향으로 6번을 움직이기 때문이다. 따라서, 가로 길이가 7 미만이면 세로가 아무리 길어도 모든 방법을 사용할 수 없다. 세로가 3이상일 때 가장 많이 움직일 수 있는 방법은 오른쪽으로 한 칸씩만 이동하는 것이기 때문에

=> 최대 방문 횟수 = min(4, 가로 길이)

 

2. 모두 사용할 수 있는 경우 - 세로 >= 3 && 가로 >= 7

N &gt;= 3 &amp;&amp; M &gt;= 7

이제 적절히 순서를 조합해서 모든 방법을 다 사용할 수 있다. 모든 방법을 한 번씩 다 사용하고 나면, 오른쪽으로 가장 많이 방문할 수 있도록 움직여서 최대 방문 횟수를 구할 수 있다.

=> 최대 방문 횟수 = 5 + (가로 길이 - 7) 

 

 

일반 구현 문제였지만 지문이 이해하기 어렵고 분기문이 많아서 쉽지 않았던 것 같네요!

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val rowLength = input[0].toInt()
    val colLength = input[1].toInt()

    when{
        // 모든 조건을 한번씩 사용할 수 없을 땐
        // 3번 이하로만 움직여서 방문 횟수를 4번 이하로 만든다.
        rowLength == 1 -> print(1)

        rowLength == 2 -> {
            val visitCount = (colLength + 1) / 2
            print( if(4 < visitCount) 4 else visitCount )
        }

        // 모든 조건을 한번 씩 써서 움직이면 가로로 6칸 이동하기 때문에
        // 가로 길이는 7이 기준이 된다.
        colLength < 7 -> print( if(4 < colLength) 4 else colLength)

        // 모든 조건을 한번씩 사용해서 움직일 수 있으므로
        // (한번씩 사용해서 방문한 횟수: 5) + (남아있는 가로 칸에서 가장 많이 움직일 수 있는 횟수)
        else -> print(5 + colLength - 7)
    }
}

 

참고

https://lipcoder.tistory.com/94