[A&I Code Camp] Day41

✍   Kotlin을 PS 문제 풀기

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

슬라이딩 윈도우

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

24499번

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

이 문제는 배열을 k 크기 부분 만큼의 합에 대한 최대를 구하는 문제입니다.

Solve

1. 배열을 n 크기 만큼 받아준다.
2. k크기 만큼의 첫 비교할 sum을 만들고 반복문을 통해 k 크기의 합을 구해준다.
3. k크기 만큼의 합을 ans에 집어넣고 반복문을 통해 sum을 구해줄 것인데
4. prefixSum[m] - prefixSum[n - 1] 부분합의 최대 공식을 이용해 부분합을 구해줄 것인데
   여기서 m은 배열의 크기를 의미하고 n은 부분합의 크기이다.
5. 그래서 다음과 같은 공식을 만들고
   sum += arr[(i + k - 1) % n] - arr[i - 1]
   ans와 sum을 비교하며 최대값이 부분합의 최대값이니 마지막에 출력해준다.

import java.io.StreamTokenizer
import kotlin.math.max

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

    val n = nextInt(); val k = nextInt()
    val arr = IntArray(n) { nextInt() }
    var sum = 0
    repeat(k) {
        sum += arr[it]
    }

    var ans = sum
    for (i in 1 ..< n) {
        sum += arr[(i + k - 1) % n] - arr[i - 1]
        ans = max(ans, sum)
    }
    println(ans)
}