BOJ : 11659 구간합구하기 (JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log

let inputs = input[0].split(' ').map(Number)
n = inputs[0]
m = inputs[1]

let lst = input[1].split(' ').map(Number)

let prefix_sum = [0]

let temp = 0

for (i of lst){
    temp +=i
    prefix_sum.push(temp)
}

let result = []

for(let i = 2 ; i < m+2 ; i++){
    let x = input[i].split(' ').map(Number)
    start = x[0]
    end = x[1]
	//c(prefix_sum[end] - prefix_sum[start-1] )
    result.push(prefix_sum[end] - prefix_sum[start-1] )

}

c(result.join('\n'))

 

풀이

누적합이라는 알고리즘을 배우게 되었다.

dp테이블때 처럼 누적합을 배열에 저장한 후 배열을 이용해 답을 구하면 된다.

 

입력1을 예시로 들면 1과 3 사이의 합을 구하는 것이니 4+3+2 를 구해야하는데 이를 구하기 위해

(5+4+3+2) - (5) 를 하면 구할 수 있다.

 

문제

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

11659번: 구간 합 구하기 4