[백준 kotlin] 1806 부분 합

문제

 

수열의 부분수열중 일정값을 넘는 부분수열의 가장 짧은 길이를 구한다.

---

풀이

투포인터를 사용하면 간단히 해결할 수 있다.
start와 end를 각각의 포인터로 하여 해결한다.

val (N, M) = readLine().split(" ").map { it.toInt() }
val nums = readLine().split(' ').map { it.toInt() }
var ans = Int.MAX_VALUE
var end = 0
var tmp = 0
var start = 0

N, M값을 입력받고 필요한 변수를 선언한다.

kotlin 에서 최대값의 경우 Int.MAX_VALUE로 설정할 수 있다.

 

while (end < N) {
        while (end < N && tmp < M) {
            tmp += nums[end]
            end++
        }

        while (tmp >= M) {
            ans = minOf(ans, end - start)
            tmp -= nums[start]
            start++
        }
    }

투포인터를 구현한 부분이다.

먼저 end < N 즉 end값이 유효한 범위를 가질 때 반복한다.

이 후 tmp < M 이라면 즉 부분수열의 합이 M값을 넘지 못한다면

현재 end값에 위치한 수를 더해주고 end 를 한칸 옮겨준다.

 

만약 부분수열의 합이 일정 값을 넘었다면

ans값을 갱신해주고

start 값을 옮기면서 이전 start값을 빼준다.

 

 

 

---

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.*
import java.util.ArrayList


fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val (N, M) = readLine().split(" ").map { it.toInt() }
    val nums = readLine().split(' ').map { it.toInt() }
    var ans = Int.MAX_VALUE
    var end = 0
    var tmp = 0
    var start = 0

    while (end < N) {
        while (end < N && tmp < M) {
            tmp += nums[end]
            end++
        }

        while (tmp >= M) {
            ans = minOf(ans, end - start)
            tmp -= nums[start]
            start++
        }
    }

    if (ans == Int.MAX_VALUE) {
        println(0)
    }else {
        print(ans)
    }
}