[A&I Code Camp] Day29

✍   Kotlin을 PS 문제 풀기

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

누적합

이번 주 주제는 누적합 알고리즘이며
백준에 하루 한 문제를 풀어가며 작성할 것입니다.
해당 내용은 위 포스트에 작성하였습니다.

3020번

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

이 문제는 각 구간별 개똥벌레의 충돌 횟수를 구해야합니다.

Solve

1. 석순과 종류석은 각각 아래에서 위로, 위에서 아래로 생성되기 때문에 주어진 입력을 이용하여 충돌 횟수를 구할 수 있어야 합니다.
2. 그래서 누적합을 통해 종유석과 석순의 충돌횟수를 쉽개 구할 수 있습니다.
3. 각 구간별 충돌 횟수를 기록할 배열을 초기화합니다. 배열은 모두 0의 값을 갖습니다.
4. 석순은 가장 아래에서 부터 자라나며 따라서 가장 아래에 1을 지정합니다. 그리고 종유석이 끝나는 지점에 -1을 지정합니다. 누적합을 실행하면 각 구간의 충돌 횟수를 쉽개 구할 수 있습니다.
5. 연산이 종료되면 각 구간을 순회하며 개똥벌레가 마주할 수 있는 가장 작은 충돌횟수를 찾아내면 됩니다.
6. 가장 먼저 최소 값을 지정한 후 해당 구간이 최소 값과 동일하다면 정답에 카운트합니다.

import java.io.StreamTokenizer

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun nextInt() : Int {
        nextToken()
        return nval.toInt()
    }

    val n = nextInt(); val h = nextInt()
    val line = IntArray(h) {0}
    repeat(n) { idx ->
        val size = nextInt()
        if (idx % 2 == 0) {
            line[h - size] += 1
        } else {
            line[0] += 1
            line[size] -= 1
        }
    }
    for (i in 1 ..< h) {
        line[i] += line[i - 1]
    }
    
    val ans = line.min(); var cnt = 0
    line.forEach { l ->
        if (l == ans) { cnt += 1 }
    }
    println("$ans $cnt")
}

📌 결론

누적합을 이해하여 문제를 풀 필요가 있다 다시 풀어봐야 할 문제이다.