[알고리즘] 부분합 (백준 1806번)

1806번: 부분합

 연속된 구간의 합이 S 이상이 되는 구간의 최소길이를 구하라는 문제다. '연속된 구간' 이라는 키워드에서 보면 알 수 있지만 무조건 투포인터 문제다.

 

Solution

1. min_length는 최소길이, sum은 list[before] ~ list[after] 까지의 구간 합이다.
2. 반복문을 돌린다.
   1. sum이 S 이상
      1. min_length를 현재 구간길이랑 비교해서 업데이트한다.
      2. before < after 이면 sum에서 list[before]를 뺸 후 before 값을 증가 시킨다.
      3. 만약 before == after가 되면 나올 수 있는 최소길이인 1이 나왔으므로 더 이상의 탐색이 불필요하기 때문에 종료시킨다.
   2. sum이 S 미만
      1. after를 증가시킨 후 sum에 list[after]를 더한다.
      2. after가 N이 되면 더 이상 sum을 S이상으로 만들 수 없다는 것이기에 종료시킨다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.min

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))


fun solution() {

    var strtok = StringTokenizer(br.readLine())

    var N = strtok.nextToken().toInt()
    var S = strtok.nextToken().toInt()

    strtok = StringTokenizer(br.readLine())

    var list = Array(N, {strtok.nextToken().toInt()})

    //구간합의 최소값
    var min_length = Int.MAX_VALUE

    var before = 0
    var after = 0

    var sum = list[0]

    while(true)
    {
        //S이상인 수이면 min 값 구하기
        if(sum >= S)
        {
            min_length = min(min_length, after - before + 1)

            if(before < after)
            {
                sum -= list[before]
                before ++
            }
            //before == after인 순간 나올 수 있는 최소길이인 1이 되므로 종료
            else
                break
        }
        else
        {
            if(after < N - 1)
            {
                after++
                sum += list[after]
            }
            //sum이 s보다 작은데 더이상 값을 추가 못하므로 종료
            else
                break
        }

    }


    if(min_length == Int.MAX_VALUE)
        bw.write("0")
    else
        bw.write(min_length.toString())
}



fun main() {
    solution()


    br.close()
    bw.close()
}