[Kotlin, S3] 백준 31883번 FA수의 진

출처: unsplash.com

 

FA수의 진(31883번)

Silver 3

#수학 #구현 #그리디 알고리즘 #시뮬레이션

 

문제 내용

 

 

문제 접근

입력이 순서대로 주어진다.

횡단보도를 건너는 시간, 육교를 건너는 시간, 횡단보도가 초록불인 시간, 횡단보도가 빨간불인 시간

위 순서대로 입력이 주어지는데, 횡단보도와 육교 중 더 시간이 적게 걸리는 방법을 찾아서 이용해야 한다. 그래야 최솟값을 구할 수 있으니.

 

횡단보도의 빨간불인 시간과 초록불인 시간을 판단을 잘해야 한다.

입력 예제 중 1가지의 예시를 불러와 보겠다.

1 2 2 4

초록불인 시간은 2분이고, 빨간불인 시간은 4초다.

이 에시를 보면 2분이 경과했을 때 횡단보도를 건널 수 있게 생겼지만 건너면 안 된다.

정확히 2분이 되는 순간 빨간불이 되기 때문에 기다려야 한다.

표로 나타내 보면 다음과 같다.

사진 1-1

시작 직후인 0분 ~ 1분까지는 초록불이지만 2분이 되는 순간부터 5분까지 빨간불 상태가 된다.

위 표를 보면 빨간불일 때도 6분까지 빨간불이 아닌, 6분이 되는 순간 초록불이 된다.

 

그러면 경과 시간에 따라 횡단보도가 빨간불인지 초록불인지 알아야 한다.

만약 빨간불이라면 얼마나 기다리면 초록줄이 되는지도 확인해야 한다.

위 입력 예제를 예로 들어 보면 총 횡단보도를 건널 때 필요한 시간은

1 + 0 또는 빨간불이 남은 시간이 될 것이다. 육교를 건너는 시간은 그냥 2이고.

이 상황에서 더 시간이 적게 걸리는 것을 택하면 문제를 해결할 수 있다.

그러면 문제를 해결하기 위해서는 경과 시간에 따른 횡단보도가 초록불인지 빨간불인지 판단해야 한다.

이를 코드를 통해 알아보자.

 

<조건 1>

일단 경과 시간을 저장할 변수가 필요하다. time으로 지정하겠다.

경과 시간에서 초록불과 빨간불의 시간의 합을 구한다. 사진 1-1을 보면 경과 시간에 따른 횡단보도 사이클을 나눈 나머지를 구하게 된다면 특정한 규칙을 찾을 수 있을 것이다. 0, 1, 6, 7일 때 횡단보도 사이클 시간인 6으로 나눈 나머지가 0, 1인 것을 확인할 수 있다. 우리는 이 사실을 바탕으로 경과 시간에서 횡단보도 사이클 시간을 나눈 나머지가 초록불이 켜지는 시간보다 작아야 한다는 것을 파악할 수 있다.

if (time % (green + red) < green)

위 조건을 만족하면 현재 횡단보도는 초록불인 상태가 될 것이다. 그러면 자연스럽게 이 조건을 만족하지 않으면 빨간불이 될 것이다.

 

<조건 2>

경과 시간에 따라 횡단보도가 초록불인지 빨간불인지 조건 1을 통해 파악했으면 이제 빨간불인 경우 남은 시간이 얼마나 되는지도 파악해야 한다. 사진 1-1을 보면 빨간불인 시간에 횡단보도 사이클을 나눈 나머지 값이 2, 3, 4, 5인 것을 알 수 있다.

만약 나머지가 2라면 빨간불이 끝날 때까지 4분을 기다려야 할 것이다. 그래야 경과 시간이 6분이 돼서 초록불로 바뀌게 될 테니.

다른 경우도 같다 3인 경우에는 3분을, 4인 경우에는 2분을, 5인 경우에는 1분을 기다리면 초록불이 된다.

바로 규칙이 보이지 않는가? 대기 시간과 나머지값의 합이 횡단보도 사이클(6분)과 동일하다.

대기 시간(빨간불일 때) + 나머지 값 = 횡단보도 사이클

 

이를 활용해 횡단보도 사이클 시간에 현재 나머지값을 빼주게 되면 대기 시간이 나올 것이다.

코드로 나타내 보자.

(green + red) - time % (green + red)

나머지 값은 조건 1에 사용한 조건 그대로 사용하면 나머지 값을 구할 수 있다.

횡단보도 사이클에서 나머지를 빼주면 남은 대기 시간을 구할 수 있을 것이다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cross = readLine().toInt()
    var time = 0

    for (i in 0 until cross) {
        val (crosswalk, viaduct, green, red) = readLine().split(" ").map { it.toInt() }

        val crossingTime = if (time % (green + red) < green) {
            0
        } else {
            // 나머지가 0이 되야 출발할 수 있다.
            (green + red) - time % (green + red)
        }

        time += min(crossingTime + crosswalk, viaduct)
    }

    println(time)
}

 

문제 풀이

입력을 횡단보도, 육교, 초록불, 빨간불 순으로 입력받고 경과 시간을 확인할 time을 생성한다.

횡단보도를 택하게 될 경우 걸릴 수 있는 대기 시간을 구해야 한다.

조건 1을 이용해 조건 1을 만족하게 되면 초록불인 경우이므로 추가적인 대기 시간은 없다. 즉 0분이다.

조건 1이 만족하지 않으면 바로 조건 2를 이용해서 남은 대기 시간을 구해야 한다. 추가 시간이 발생한다.

최종적으로 crossingTime은 0 또는 추가 시간이 될 것이다.

 

이제 time에서 육교를 건너는 시간(viaduct)과 횡단보도를 건너는 시간에서 추가 시간을 더한 시간(crossingTime + crosswalk)에서 더 작은 값을 택해서 그만큼 time을 늘려준다.

그럼 최적의 시간으로 모든 길을 건널 수 있다.

 

 

문제 해결 과정

사칙 연산과 나머지로 빨간불일 때의 남은 대기 시간을 구하는 게 핵심이다. 또한 문제 조건에 있다시피 정확히 시간에 횡단보도에 도달하게 되면 신호등이 바뀌기 때문에 그것도 생각해야 한다.

그거 말고는 평범한 그리디 알고리즘 문제이다.