[백준] 1806 부분합

문제

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

 

입력

n: Int = 수열의 길이
s: Int = 부분합 기준
arr: [Int] = 수열

10 <= n <= 100,000
0 < s < 100,000,000
1 <= arr[i] <= 10,000

결과

ans: Int = 부분합이 s이상이 되는 것 중 가장 짧은 길이

해석

왼쪽부터 오른쪽으로 한칸씩 전진하며 sum이 s이상이 되었을 때 길이를 저장하고

왼쪽 포인터를 하나 움직여 sum을 다시 낮춰준다.

코드

import Foundation

let ns = readLine()!.split{$0 == " "}.map{Int($0)!}

let (n,s) = (ns[0], ns[1])

let arr = readLine()!.split{$0 == " "}.map{Int($0)!}

var dist: Int = Int.max

var left: Int = 0
var right: Int = 0

var sum = 0

while left <= right {
    
    if sum >= s {
        dist = min(dist,right-left)
        sum -= arr[left]
        left += 1
    } else if right == n  {
        break
    } else {
        sum += arr[right]
        right += 1
    }
}


print(dist == Int.max ? 0 : dist)