<백준> 24.05.30에 푼 문제들

1. 지름길 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/1446 지름길 at main · heesoo-park/ForCodeKata

제출 결과

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

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

data class Info(
    val start: Int,
    val len: Int
)

private val result = IntArray(10001)
private val shortCuts = Array(10001) { mutableListOf<Info>() }

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    val (n, d) = br.readLine().split(' ').map { it.toInt() }
    repeat(n) {
        val shortCut = br.readLine().split(' ').map { it.toInt() }
        if (shortCut.any { it > d }.not()) shortCuts[shortCut[1]].add(Info(shortCut[0], shortCut[2]))
    }
    
    for (i in 1..d) {
        result[i] = result[i - 1] + 1
        for (j in shortCuts[i]) {
            result[i] = minOf(result[i], result[j.start] + j.len)
        }
    }
    
    bw.write("${result[d]}")
    bw.flush()
    bw.close()
}

(처음에는 BFS라고 생각했지만 케이스가 감당할 수 없다는 걸 알고 DP로 생각을 바꿨다. 하지만 쉽게 풀리지 않았고 참고해서 해결했다. 여기서 알게 된 건 인접 리스트를 구성할 때 출발점을 기준으로 하는 게 아니라 도착점을 기준으로 할 수 있다는 아이디어다.)

 

2. 볼 모으기 (Silver 1)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/17615 볼 모으기 at main · heesoo-park/ForCodeKata

제출 결과

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

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

private const val left = 0
private const val right = 1

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    val n = br.readLine().toInt()
    val balls = br.readLine()
    
    val redCount = balls.count { it == 'R' }
    val blueCount = n - redCount
    var result = minOf(redCount, blueCount)
    
    result = minOf(result, calCount(n, balls, 0))
    result = minOf(result, calCount(n, balls, 1))
    
    bw.write("$result")
    bw.flush()
    bw.close()
}

fun calCount(n: Int, balls: String, dir: Int): Int {
    var isDivided = false
    var cnt = 0
    
    if (dir == right) {
        val c = balls[n - 1]
        for (i in n - 1 downTo 0) {
            if (balls[i] != c) isDivided = true
            if (isDivided && balls[i] == c) cnt++
        }
    } else {
        val c = balls[0]
        for (i in 0 until n) {
            if (balls[i] != c) isDivided = true
            if (isDivided && balls[i] == c) cnt++
        }
    }
    
    return cnt
}

(최근에 많이 접하고 있는 그리디 알고리즘 문제다. 이번에도 최대한 단순하게 생각해서 해결했는데 가장 큰 단서는 '좌우 끝에 있는 공의 색이 무엇인가?'였다. 그거에 맞춰 움직임이 생기는 공의 개수를 카운트했다.)