<백준> 24.06.05에 푼 문제들

1. 회전 초밥 (Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/2805 나무 자르기 at main · heesoo-park/ForCodeKata

제출 결과

작성한 코드는 다음과 같다.

import java.io.*
import java.util.*
import kotlin.math.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    val (n, m) = br.readLine().split(' ').map { it.toInt() }
    val trees = br.readLine().split(' ').map { it.toInt() }
    
    var low = 0
    var high = trees.max()!!
    while (low <= high) {
        val mid = (low + high) / 2
        
        var sum: Long = 0L
        for (tree in trees) {
            if (tree > mid) sum += (tree - mid)
        }
        
        if (sum >= m) {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    
    bw.write("$high")
    bw.flush()
    bw.close()
}

(sum의 범위만 잘 설정하면 쉬운 문제였고, kotlin에서 max()를 쓸 때마다 Int?로 캐스팅이 되서 조금 불편하다... 그냥 타입을 지정해주는게 좋을까?)

 

2. 입국심사 (Gold 5)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/3079 입국심사 at main · heesoo-park/ForCodeKata

제출 결과

작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    val (n, m) = br.readLine().split(' ').map { it.toInt() }
    val counters = List<Long>(n) { br.readLine().toLong() }
    
    var low: Long = 1
    var high: Long = m.toLong() * counters.max()!!
    var result: Long = 0
    while (low <= high) {
        val mid: Long = (low + high) / 2
        
        var sum: Long = 0L
        for (counter in counters) {
            sum += (mid / counter)
            if (sum > m) break
        }
        
        if (sum >= m) {
            if (result > mid || result == 0L) result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    
    bw.write("$result")
    bw.flush()
    bw.close()
}

(이분탐색 문제였고 걸리는 시간을 기준으로 하면 되겠다는 거까지는 금방 도달했다.)

(하지만 심사대에 대한 계산을 어떻게 해야할지 몰라 시간이 오래 걸렸고 도움을 받았다.)

(Long에 제대로 데이고, break 안 걸어서 오버플로우에 데이고, high의 초기값을 작게 잡았다가 데이는 등 다양하게 데였다...)

(어렵다 싶은 문제들은 보통 관점을 반대로 뒤집거나 적절한 알고리즘만 떠올린다면 쉽게 풀리는 거 같다... 그게 잘 안 돼서 그렇지)

 

참고)

https://hagisilecoding.tistory.com/38