글 읽기 - 무슨 차이로 하나는 시간초과이고 하나는 정답인 것인지 모르겠습니다.

hsjeon01 1년 전 0

아래의 두 가지 코드의 차이점이라고는 1번 코드는 2중 반복문을 함수로 구현하여 사용한 것이고 2번 코드는 그것을 함수로 사용하지 않고 그냥 for문 안에서 사용한 것뿐입니다...왜 1번 코드는 정답이고 2번 코드는 1%에서 시간초과가 발생하는지 모르겠습니다.ㅜㅜ 고수님들 도와주세요..! 감사합니다!

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

fun main(){


    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val ground = mutableListOf<MutableList<Int>>()

    val input = br.readLine().split(" ").map { it.toInt() }
    val col = input[0] // 세로
    val row = input[1] // 가로
    var inven = input[2] // 인벤토리에 있는 블럭의 수
    var timeAndHeight = IntArray(2, {999999999})



    repeat(col){
        val Info = br.readLine().split(" ").map { it.toInt() }.toMutableList()
        ground.add(Info)
    }

    var max = 0
    var min = 999999999
    ground.forEach { col ->
        col.forEach {
            if (it < min) min = it
            if (it > max) max = it
        }
    }
    for (std in min .. max){
        val digAndPut = digAndPut(ground,std,inven)
        if (digAndPut <= timeAndHeight[0]){
            timeAndHeight[0] = digAndPut
            timeAndHeight[1] = std
        }

    }
    bw.write("${timeAndHeight[0]} ${timeAndHeight[1]}")
    bw.flush()
    bw.close()

}
fun digAndPut(ground : MutableList<MutableList<Int>>, std : Int, inven : Int) : Int{
    var time = 0
    var blockCanuse = inven
    for (col in 0 until ground.size){

        for (row in 0 until ground[col].size){
            var cur = ground[col][row]
            if (cur < std){
                time += (std - cur)
                blockCanuse -= (std - cur)
            }
            else if (cur > std){
                time += 2 * (cur - std)
                blockCanuse += (cur - std)
            }
        }
    }
    if (blockCanuse < 0) return 999999999
    return time
}

// 아래의 코드는 시간초과를 발생시킵니다. 1퍼센트에서요...
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main(){


    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val ground = mutableListOf<MutableList<Int>>()

    val input = br.readLine().split(" ").map { it.toInt() }
    val col = input[0] // 세로
    val row = input[1] // 가로
    var inven = input[2] // 인벤토리에 있는 블럭의 수
    var timeAndHeight = IntArray(2, {999999999})



    repeat(col){
        val Info = br.readLine().split(" ").map { it.toInt() }.toMutableList()
        ground.add(Info)
    }

    var max = 0
    var min = 999999999
    ground.forEach { col ->
        col.forEach {
            if (it < min) min = it
            if (it > max) max = it
        }
    }
    for (std in min .. max){
        var time = 0
        var blockCanuse = inven
        for (col in 0 until ground.size){

            for (row in 0 until ground[col].size){
                var cur = ground[col][row]
                if (cur < std){
                    time += (std - cur)
                    blockCanuse -= (std - cur)
                }
                else if (cur > std){
                    time += 2 * (cur - std)
                    blockCanuse += (cur - std)
                }
            }

        }
        if (blockCanuse < 0) continue
        if (time <= timeAndHeight[0]){
            timeAndHeight[0] = time
            timeAndHeight[1] = std
        }
    }
    bw.write("${timeAndHeight[0]} ${timeAndHeight[1]}")
    bw.flush()
    bw.close()

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

무슨 차이로 하나는 시간초과이고 하나는 정답인 것인지 모르겠습니다.

hsjeon01 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말