연습장/백준(BOJ) 문제풀이
[백준 11659] 구간 합 구하기 4 with Node.js
Tesseractjh
2021. 8. 9. 12:47
문제 링크
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
풀이
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까지의 합과 같다.