[백준/코틀린] 5525번: IOIOI

링크

5525번: IOIOI

풀이

dp[i]: i에서 시작하는 "IOI" 패턴의 연속 횟수

문자열을 뒤에서 앞으로 탐색하며 [i, i+2] 구간이 "IOI" 패턴인지 확인합니다.
"IOI" 패턴이 성립하면, i+2 위치에서 이어진 "IOI" 패턴의 연속 횟수에 1을 더해 dp[i]를 갱신합니다.

즉, dp[i] ≥ n이면 해당 위치에서 PN이 등장함을 알 수 있습니다.

코드

fun main() {
    val n = readln().toInt()
    val m = readln().toInt()
    val s = readln()
    val dp = IntArray(m)

    (m - 3 downTo 0).forEach {
        if (s.slice(it..it + 2) == "IOI") {
            dp[it] = dp[it + 2] + 1
        }
    }

    println(dp.count { it >= n })
}