[백준] 14936번 엘리베이터 장난

14936번 엘리베이터 장난

접근방법

1. 완전탐색으로 접근
   • 시간초과
   • 최대개수 100,000
2. Filter를 이용하여 접근
   • 시간 초과
   • 최대 10만개의 경우 filter, map 등 추가적인 작업이 많아 100만 횟수가 넘는다고 판단했슴
3. 수학적 접근
   • 같은 곳을 두 번 누르면 초기 상태인 점에서 착안하여 나올 수 있는 경우의 수 고려
   • 각 경우마다 걸리는 시간을 계산하여 주어진 시간내에 할 수 있는지 확인
   • 할 수 있는 경우에 경우의 수 +1
   • N이 작은 경우에 동작이 겹치는 경우 존재함
   • N == 1이면, 전체를 키는 동작과 홀수를 키는 동작은 동일한 동작이므로 분기처리
   • N <= 2이면, 홀수를 키는 동작과 3K+1을 키는 동작은 동일한 동작이므로 분기 처리
   • 또한 짝수는 2부터 있으므로 N > 1 을 추가

Code

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

class IO14936 {
    private val bw = BufferedWriter(OutputStreamWriter(System.out))
    private val br = BufferedReader(InputStreamReader(System.`in`))

    fun getNM() = br.readLine().split(" ").map { it.toInt() }
    fun write(message: String) = bw.write(message)
    fun flush() = bw.flush()
    fun close() = bw.close()
}

fun main() {
    var ans = 1

    val io = IO14936()
    val (N,M) = io.getNM()

    val all = N
    val odd = if(N%2 == 0)  N/2 else N/2+1
    val even = N/2
    val k3 = N/3 + if (N%3 >= 1) 1 else 0

    if (M >= all) { ans ++ }
    if (M >= odd && N > 1) { ans++ }
    if (M >= even && N > 1) { ans++ }
    if (M >= k3 && N > 2) { ans++ }
    if (M >= k3 + odd && N > 2) { ans++ }
    if (M >= k3 + even && N > 2) { ans++ }
    if (M >= k3 + all && N > 2) { ans++ }

    io.write(ans.toString())
    io.flush()
    io.close()
}