[백준 11659] 구간 합 구하기 4 with Node.js

문제 링크

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

11659번: 구간 합 구하기 4

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const arr = input[1].split(' ').map(v => +v);
const cumsum = new Array(arr.length+1).fill(0);
const output = [];

arr.forEach((v, i) => {
  cumsum[i+1] = cumsum[i] + v;
});


input.slice(2).forEach(ij => {
  const [i, j] = ij.split(' ').map(v => +v);
  output.push(cumsum[j]-cumsum[i-1]);
});

console.log(output.join('\n'));

처음에 무작정 arr의 i번째 부터 j번째 수를 더하여 출력하였더니 시간 초과가 났다.

 

cumsum 배열을 만들어서 arr의 누적합을 저장한다.

cumsum[j]에서 cumsum[i-1]을 뺀 값이 곧 arr의 i~j까지의 합과 같다.