<백준> 24.05.22에 푼 문제들

1. 햄버거 분배(Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/햄버거 분배 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, k) = br.readLine().split(' ').map { it.toInt() }
    val table = br.readLine()
    val visited = BooleanArray(n) { false }
    
    var result = 0
    for (i in 0 until n) {
        if (table[i] != 'P') continue
        
        for (j in i - k..i + k) {
            if (j !in 0 until n || j == i) continue
            
            if (table[j] == 'H' && !visited[j]) {
                visited[j] = true
                result++
                break
            }
        }
    }
    
    bw.write("$result")
    bw.flush()
    bw.close()
}

(아주 예전에 풀었었던 체육복 빌려주는 문제가 생각나서 금방 풀었다.)

 

2. 진우의 달 여행 (Small) (Silver 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/진우의 달 여행 (Small) at main · heesoo-park/ForCodeKata

제출 결과

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

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

const val INF = Int.MAX_VALUE

private lateinit var space: Array<IntArray>
private val dp = Array(6) { Array(6) { IntArray(3) { INF }}}

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() }
    space = Array(n) { IntArray(m) }
    
    for (i in 0 until n) {
        val line = br.readLine().split(' ').map { it.toInt() }
        for (j in 0 until m) {
            space[i][j] = line[j]
        }
    }
    
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (i == 0) {
                dp[i][j][0] = space[i][j]
                dp[i][j][1] = space[i][j]
                dp[i][j][2] = space[i][j]
                continue
            }
            
            when (j) {
                0 -> {
                    dp[i][j][0] = minOf(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + space[i][j]
                    dp[i][j][1] = dp[i - 1][j][0] + space[i][j]
                }
                m - 1 -> {
                    dp[i][j][1] = dp[i - 1][j][2] + space[i][j]
                    dp[i][j][2] = minOf(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + space[i][j]
                }
                else -> {
                    dp[i][j][0] = minOf(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + space[i][j]
                    dp[i][j][1] = minOf(dp[i - 1][j][0], dp[i - 1][j][2]) + space[i][j]
                    dp[i][j][2] = minOf(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + space[i][j]
                }
            }
        }
    }
    
    var result = INF
    for (j in 0 until m) {
        for (d in 0 until 3) {
            result = minOf(result, dp[n - 1][j][d])
        }
    }
    
    bw.write("$result")
    bw.flush()
    bw.close()
}

(DP로 풀 수 있겠다는 거는 금방 알았는데 3차원 상에서 로직을 구체화시키는 것에서 실패했다가 도움을 받아 해결해냈다...)

 

참고)

https://velog.io/@gkdbssla97/BOJ-17484.-%EC%A7%84%EC%9A%B0%EC%9D%98-%EB%8B%AC-%EC%97%AC%ED%96%89-Small-Java

 

3. 비슷한 단어 (Silver 2)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/비슷한 단어 at main · heesoo-park/ForCodeKata

제출 결과

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

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

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = br.readLine().toInt()
    var result = n - 1

    val firstWord = br.readLine()
    val first = firstWord.groupingBy { it }.eachCount()
    repeat(n - 1) {
        val curWord = br.readLine()
        val cur = curWord.groupingBy { it }.eachCount()

        var cnt = 0
        var isDoubled = false
        for (i in first.keys.union(cur.keys)) {
            if (cur.containsKey(i) && first.containsKey(i)) {
                val diff = abs(first[i]!! - cur[i]!!)
                cnt += diff
                if (diff >= 2) isDoubled = true
            } else if (cur.containsKey(i)) {
                cnt += cur[i]!!
            } else if (first.containsKey(i)) {
                cnt += first[i]!!
            }
        }

        if (cnt > 2) {
            result--
        } else if (cnt == 2) {
            if (isDoubled) {
                result--
            } else if (firstWord.length != curWord.length) {
                result--
            }
        }
    }

    bw.write("$result")
    bw.flush()
    bw.close()
}

(배열을 썼으면 좀 더 빠른 결과가 나왔을텐데 Map을 사용하다보니 좀 시간이 더 걸린 거 같고 많은 예외케이스를 생각하고 비슷한 단어를 찾는게 아니라 비슷하지 않은 단어를 찾는 방향으로 하다보니 좀더 헷갈렸다.)