백준 - 물 주기(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/23351

 

[문제 설명]

캣닢이 시드는 첫번째 날을 구하시오.

[접근 방법]

모든 화분에 물은 동일하므로, 화분에 물을 주는 주기는 전부 비슷하다.

각 화분은 물을 주는 주기가 되기 전까지는 -1씩 물이 준다.

주기가 되면, 화분에 (B-1)만큼 수분이 추가 된다.

따라서, 모든 배열을 체크할 필요 없이 마지막 화분을 기준으로 생각하면 간단하다.

시간복잡도는 Day가 정답이고, 주기는 N/A => cycle이라고 두면

O(K+(Day/cycle))이 아닐까 싶다. 사실 조건에 따라 평생 정답이 안 나올 수도 있지만, 정답이 있다는 가정하에 푸는 문제이므로 Day가 나오기 때문에 풀 수 있는 문제다.

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (N,K,A,B) = readLine().split(" ").map {it.toInt()}
    // 현재 날짜
    var day = 0
    // 마지막 화분에 남은 물
    var restWater = K
    // 화분에 물을 주는 주기
    val cycle = N/A
    // 화분에 물이 다 마르면 종료
    while (0 < restWater) {
        day++
        // 주기마다 물을 주고, 1이 증발한다.
        if ((day)%cycle == 0) {
            restWater += (B-1)
        } else {
            restWater--
        }
    }
    
    println(day)
}