[A&I Code Camp] Day28

✍   Kotlin을 PS 문제 풀기

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

누적합

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

21758번

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

이 문제는 꿀통의 위치에서 가능한 최대의 꿀의 양을 구해 출력하는 문제입니다.

Solve

1. 꿑통의 크기와 배열을 받고 꿀통의 누적합을 구해놓습니다.

2. 벌통에 꿀이 가장 많은 경우는 3가지 경우가 있을 수 있습니다.
   2-1. 벌통이 오른쪽 끝에 있는 경우
   2-2. 벌통이 왼쪽 끝에 있는 경우
   2-3. 벌통이 가운데 있을 때 경우에서 최대값.

3. 하나씩 ans안에 넣어주고 max() 연산자를 통해 비교한 뒤 가장 많은 꿀의 양을 구해줍니다.

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

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

    //1. 입력을 받는다.
    val n = nextInt()
    val pSum = IntArray(n+1) {0}
    //꿀통의 배열
    val arr = IntArray(n) {
        nextInt()
    }
    //꿀 배열의 누접합을 구해서 연산을 수행
    for (i in 1 .. n) {
        pSum[i] = pSum[i - 1] + arr[i]
    }


    //2. 벌이 꿀을 채취할 수 있는 경우의 수를 순회
    var ans = 0
    //2-1. 벌통이 오른쪽 끝에 있는 경우
    for (i in 2 ..< n) {
        //arr은 자기 자신의 위치를 채취하지 못함
        val left = pSum[n] - pSum[1] - arr[i - 1]
        val right = pSum[n] - pSum[i]
        val total = left + right
        ans = max(ans, total)
    }

    //2-2. 벌통이 왼쪽 끝에 있는 경우
    for (i in 2 ..< n) {
        val right = pSum[n - 1] - arr[i - 1]
        val left = pSum[i]
        val total = right + left
        ans = max(ans, total)
    }

    //2-3. 벌통이 가운데 있을 때 경우에서 최대값.
    for (i in 2 ..< n) {
        //pSum[i - 1]은 벌통의 위치
        val total = pSum[i] - pSum[1] + pSum[n - 1] - pSum[i - 1]
        ans = max(ans, total)
    }

    println(ans)
}