[Swift 백준] 11659 구간 합 구하기 4

 

풀이 아이디어

누적 합 문제입니다.

평소 풀어보지 않은 유형이라 문제를 보고 생각나는 대로 풀었더니 시간 초과가 났습니다.

 

누적 합 문제의 기본 골자는 다음과 같습니다.

1. 각 원소의 누적 합을 미리 구해둔다.

2. 임의의 수 n부터 m까지의 누적합은  m까지의 누적합에서 n - 1까지의 누적합을 뺀 것과 같습니다.

 

공식의 숙지가 필요한 문제였습니다.

마치 dp 테이블을 미리 채워놓는것과 비슷한 느낌인 거 같아요

 

풀이

let n = Int(readLine()!)!

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

let m = Int(readLine()!)!

// 인덱스 계산하기 쉽게 0을 채워줍니다
var prefix = [0] + Array(repeating: 0, count: n)
for i in 1...n {
    //인덱스 주의
    prefix[i] = prefix[i-1] + arr[i-1]
}

for _ in 0..<m {
    let ij = readLine()!.split(separator: " ").map { Int($0)! }
    let (i, j) = (ij[0], ij[1])
    
    print(prefix[j] - prefix[i-1])
}