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

문제

 

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

11659번: 구간 합 구하기 4

 

 

풀이

 

당연하게 반복문을 통해 하나씩 더해서 출력하는건 시간초과가 난다.

 

dp문제인 것을 알기때문에 그 방향으로 접근해보면, result[k]는 k번째까지의 수를 더한 값이다. 

a번째 수부터 b번째 수까지 전부 더한다면 a + (a + 1) ...+ b - 1+ b 이렇게 될 것이다. 이것을 통해 식을 생각해보면 

 

a번째 수부터 b번째 수까지 더한 값은 result[b] - result[a - 1]이다.

 

a - 1인 것은 당연히 a이전까지는 더하는 것이 아니기때문이다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = input[1]
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }
var result = Array(repeating: 0, count: numbers.count + 1)
for i in 1...numbers.count {
    result[i] = result[i - 1] + numbers[i - 1]
}
for _ in 0..<m {
    let section = readLine()!.split(separator: " ").map { Int(String($0))! }
    print(result[section[1]] - result[section[0] - 1])
}

 

 

_____________________________________________________________________________________________________

 

 

아직까진 어떤 문제들이 dp인지 잘 모르겠음