[Kotlin, S2] 백준 26007번 Codepowers

출처: unsplash.com

 

Codepowers(26007번)

Silver 2

# 누적 합

 

문제 내용

 

 

문제 접근

각 쿼리는 시작 라운드(포함), 종료 라운드(미포함)의 사이에 진행된 라운드마다의 현재 레이팅을 구해서 k보다 낮은 레이팅의 개수를 구해서 출력하면 된다.

 

문제 내용은 단순하지만 왜 silver 2씩이나 받았는지 생각해봐야 한다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    // n: round, x: 초기 레이팅, m: 쿼리의 개수, k: 낮은 레이팅 기준점
    val (n, m, k, x) = bf.readLine().split(" ").map { it.toInt() }
    val a = StringTokenizer(bf.readLine())
    val rating = Array(n + 1) { 0 }
    var score = x
    rating[0] = if (score < k) 1 else 0

    for (i in 1 until rating.size) {
        score += a.nextToken().toInt()
        rating[i] = if (score < k) rating[i - 1] + 1 else rating[i - 1]
    }

    val answer = StringBuilder()
    for (i in 0 until m) {
        val (l, r) = bf.readLine().split(" ").map { it.toInt() }

        answer.append("${rating[r - 1] - rating[l - 1]}\n")
    }

    println(answer)
}

 

문제 풀이

score를 a의 입력값과 더해서 라운드 진행 후의 rating을 구하고, 따로 rating array를 만들어 1라운드부터 i라운드까지 k보다 작은 레이팅이 있는 라운드의 개수를 세준다.

k보다 작으면 이전 값에 1을 더하고 아니면 이전 값을 가져온다.

 

다음으로 쿼리를 입력받아 l 라운드부터 r 라운드 직전까지의 rating이 k보다 작은 개수를 구하는 방법은 rating의 r - 1번째 index에 l - 1번째 index를 빼면 구할 수 있다.

 

 

문제 해결 과정

기존에는 rating에 각각의 라운드 종료 후의 rating을 저장해 주고, 쿼리에서 l 번부터 r번까지의 index를 for로 탐색해 개수를 구해주었다.

하지만 시간 초과가 발생했다.

위처럼 단순하게 구현을 하면 시간 초과가 발생한다.

 

누적 합을 이용해 주자.

rating의 0번째 값은 현재 x가 k보다 작으면 1, 아니면 0이다.

그다음의 1번째 index부터는 갱신된 score값이 k보다 작으면 이전 값에 1을 더해서 넣고, 그렇지 않으면 이전 값을 가져온다.