[Swift] 백준 2559 : 수열

문제

# 풀이

전형적인 누적합 문제.

아래와 같이 psum[0] = 0 부터 시작하는 prefix sum을 먼저 구한 뒤

var psum = [Int](repeating: 0, count: n + 1)

for i in 1...n {
    psum[i] = psum[i-1] + inputArr[i-1]
}

 

psum[m] - psum[0] 부터 psum[n] - psum[n-m] 중 가장 작은 값을 찾는다.

var max = Int.min;
for i in m...n {
    if( max < psum[i] - psum[i-m] ) {
        max = psum[i] - psum[i-m]
    }
}

 

소스코드

import Foundation

let input = readLine()!.split(separator: " ").map{Int($0)!}

let n = input[0], m = input[1]

let inputArr = readLine()!.split(separator: " ").map{Int($0)!}

var psum = [Int](repeating: 0, count: n + 1)

for i in 1...n {
    psum[i] = psum[i-1] + inputArr[i-1]
}

var max = Int.min;
for i in m...n {
    if( max < psum[i] - psum[i-m] ) {
        max = psum[i] - psum[i-m]
    }
}
print(max)