[백준 27210] - 신을 모시는 사당(Kotlin)[골드5]

문제

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

27210번: 신을 모시는 사당

 

문제 풀이

같은 방향의 돌상의 길이가 가장 큰 구간을 구하는 전형적인 누적합 문제였습니다.

나는 두 개의 변수를 사용해서 각기 다른 돌상의 개수를 계산했습니다.

 

왼쪽 돌상의 개수를 left, 오른쪽 돌상의 개수를 right로 관리했습니다.

입력을 탐색하면서, 왼쪽 돌상이라면 left ++, right -- 오른쪽 돌상이라면 right++, left--를 해줬습니다.

추가적으로 우리는 연속적인 구간의 최대합을 원하기 때문에 left와 right가 음수라면 0으로 초기화해 줬습니다.

자세한 설명은 그림과 같이 설명 설명해 보겠습니다.

 

먼저 left와 right가 음수가 되면 0으로 초기화하는 이유에 대해서 설명하겠습니다.

우리는 연속적인 구간의 최대 길이 합을 구해야 합니다.

하지만 구간의 합이 음수라면 그 구간은 버리면 되는 것입니다.

예를 들어 2가 처음 등장하는 4번 index의 경우 4번 index의 동상부터 칠하는 것입니다.

그리고 만약 값이 음수가 아니라면 4번 index~ 5번 index까지의 left값처럼 누적합에서 빼주면 됩니다.

 

전체 코드

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private var answer = 0
    fun run() {
        input()
        print(answer)
    }

    private fun input() {
        n = br.readLine().toInt()
        val line = br.readLine().split(" ").map { it.toInt() }
        var left = 0
        var right = 0
        for (i in 0 until line.size) {
            if (line[i] == 2) {
                right++;
                left--
            } else {
                left++;
                right--
            }
            if (left < 0) {
                left = 0
            }
            if (right < 0) {
                right = 0
            }
            answer = Math.max(answer, Math.max(left, right))
        }
    }
}

fun main() {
    val solution = Solution().run()
}