[백준11659_자바스크립트(javascript)] - 구간 합 구하기 4

🔴 문제

구간 합 구하기 4

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n, m] = inputs.shift();
const numbers = inputs.shift();
const dp = Array(n + 1).fill(0);

for (let i = 1; i <= n; i++) {
  dp[i] = dp[i - 1] + numbers[i - 1];
}

for (const input of inputs) {
  const [start, end] = input;
  console.log(dp[end] - dp[start - 1]);
}

🟢 풀이

⏰ 소요한 시간 : -

dp 구간합 문제.... ! 다음과 같은 점화식을 적으면 구간합을 구할 수 있다.

dp[i] = dp[i - 1] + numbers[i - 1]

🔵 Ref