[A&I Code Camp] Day49

✍   Kotlin을 PS 문제 풀기

소속중인 A&I 동아리에서 코딩역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 kotlin을 기반으로 작성합니다.

구현

이번 주 주제는 구현입니다.
백준에 하루 한 문제를 풀어가며 작성할 것입니다.

18111번

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

이 문제는 n * m 크기의 땅이 있을 때 나에게 주어진 블록은 B개가 있으며
그 때 최대 높이를 만드는데의 시간과 최대 높이를 구하는 문제입니다.
여기서 블록을 놓을 때는 1초가 걸리며
블록을 파는데는 2초의 시간이 걸립니다.
또한 블록이 부족하면 작업이 불가할 시 최대 높이에 따라
파는 방법도 생각해야 합니다.

Solve

1. 입력을 받습니다.

    fun nextInt() : Int { nextToken(); return nval.toInt() }

    val n = nextInt(); val m = nextInt(); val b = nextInt()
    val mine = Array(n){ IntArray(m) {nextInt()} }

2. 배열에 따른 최대 높이와 최소 높이를 구해줍니다.

    var minH = 257
    var maxH = 0

    for(i in 0 ..< n){
        for(j in 0 ..< m){
            val height = mine[i][j]
            maxH = max(maxH, height)
            minH = min(minH, height)
        }
    }

3. 파는 데는 2초 놓는 데에는 1초가 걸리는 조건을 생각하며
   최소 시간과 결과 높이를 변수로 두고 최소 높이부터 최대 높이까지 반복을 만들어 준다.
   이때 inven에 있는 블록 갯수를 소유한 블록 b로 두고
   시간은 0으로 초기화 해줍니다.
   3-1. n * m의 2중 반복을 돌 것인데 만약 내 땅 mine의 [x][y]가 높이 h보다
   작다면 블록을 놔야하니 time에는 drop한 블록의 갯수만큼 더해주고
   inven에는 drop한 블록의 갯수를 빼줍니다.
   3-2. 반대의 경우에는 블록을 파야하는 경우로 time에는 2배의 시간이 걸리니
   drop한 블록의 갯수에 2를 곱해주고 inven에는 판 블록의 수 drop을 더해줍니다.

    var minTime = Int.MAX_VALUE
    var resultH = 0

    for(h in minH .. maxH){
        var inven = b
        var time = 0

        for(x in 0 ..< n){
            for(y in 0 ..< m){
                if(mine[x][y] < h){
                    //3-1. 높이보다 작기에 블록을 놓아야함.
                    val drop = h - mine[x][y]
                    time += drop
                    inven -= drop
                } else if(mine[x][y] > h){
                    //3-2. 높이보다 크기에 파야함.
                    val drop = mine[x][y] - h
                    time += drop * 2
                    inven += drop
                }
            }
        }

4. 만약 작업이 불가능 할 시 블록을 파는 경우도 생각해야 합니다.
   inven에 블록이 음수로 가면 평탄화가 불가능 하단 것이니
   minTime에 현재 작업한 time을 할당하고
   출력할 resultH에 작업한 현재 높이 값을 저장해야 합니다.

//4. 작업 불가능시 블록을 파는 경우의 수
        if(inven >= 0 && time <= minTime) {
            minTime = time
            resultH = h
        }

전체 코드

import java.io.StreamTokenizer
import kotlin.math.*

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())){
    //1. 입력받기
    fun nextInt() : Int { nextToken(); return nval.toInt() }

    val n = nextInt(); val m = nextInt(); val b = nextInt()
    val mine = Array(n){ IntArray(m) {nextInt()} }

    //2. 최대, 최소 높이 구하기
    var minH = 257
    var maxH = 0

    for(i in 0 ..< n){
        for(j in 0 ..< m){
            val height = mine[i][j]
            maxH = max(maxH, height)
            minH = min(minH, height)
        }
    }

    //3. 파는데 걸리는 건 2초, 놓는데 걸리는 것은 1초
    var minTime = Int.MAX_VALUE
    var resultH = 0

    for(h in minH .. maxH){
        var inven = b
        var time = 0

        for(x in 0 ..< n){
            for(y in 0 ..< m){
                if(mine[x][y] < h){
                    //3-1. 높이보다 작기에 블록을 놓아야함.
                    val drop = h - mine[x][y]
                    time += drop
                    inven -= drop
                } else if(mine[x][y] > h){
                    //3-2. 높이보다 크기에 파야함.
                    val drop = mine[x][y] - h
                    time += drop * 2
                    inven += drop
                }
            }
        }

        //4. 작업 불가능시 블록을 파는 경우의 수
        if(inven >= 0 && time <= minTime) {
            minTime = time
            resultH = h
        }
    }
    println("$minTime $resultH")
}