[백준] 2559 수열 (코틀린 kotlin)

 

문제 링크

 

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

2559번: 수열

 

 

 

문제 풀이

 

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(" ").map { it.toInt() }
    val temperature = readLine().split(" ").map { it.toInt() }.toIntArray()
    var sum = temperature.slice(0 until k).sum()
    var max = sum

    for (i in k until n) {
        sum = sum - temperature[i - k] + temperature[i]
        max = kotlin.math.max(max, sum)
    }
    println(max)
}

 

 

슬라이딩 윈도우 유형을 이해하기에 좋은 문제였습니다.

k가 3라고 가정했을 때 

(0, 1, 2)번째 합, (1, 2, 3)번째 합, (2, 3, 4)번째 합 ... (n - 3, n - 2, n - 1)번째 합 중 최댓값을 찾아야합니다.

모든 부분 수열의 합을 구할 때마다 더하기 연산을 하는 것보다

이전 합에서 가장 앞의 값을 빼고 가장 뒤의 값을 더해주는 2번의 연산만 해주는 것이 효율적입니다.

이렇게 이전 연산에서 가장 인덱스가 작은 값을 빼주고 다음 순서의 인덱스 값을 더해주며

고정된 크기의 슬라이드를 이동하며 계산해나가는 유형이 슬라이딩 윈도우 유형입니다.

이를 구현하기 위해, sum이라는 변수에 k번째까지의 값을 slice한 부분 수열의 합을 대입해놓고,

max 값을 이 값으로 초기화시켜줍니다.

이후, sum 변수의 값에서 가장 앞 값을 빼고 다음 인덱스의 값을 더하는 연산을 마지막 원소가 더해질 때까지 반복하며

max 값을 갱신시킵니다.