[JavaScript/DP] 백준 실버 3 : 11659 - 구간 합 구하기

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

11659번: 구간 합 구하기 4

---

📌 작성한 코드

// 11659
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map(Number);
const list = input.shift().split(" ").map(Number);
const intervals = input.map((str) => str.split(" ").map(Number));

const dp = new Array(N + 1).fill(0);
dp[1] = list[0];
for (let i = 2; i <= N; i++) {
    dp[i] = dp[i - 1] + list[i - 1];
}

let answer = "";
intervals.forEach(([i, j]) => {
    answer += `${dp[j] - dp[i - 1]}\n`;
});

console.log(answer);

📌 풀이 

(1) 0부터 i까지의 합을 dp를 통해 구한다.

- 정의 : dp[i] = 1번 숫자부터 i번 숫자까지의 합

- 점화식 : dp[i] = dp[i-1]+ list[i]

const dp = new Array(N + 1).fill(0);
dp[1] = list[0];
for (let i = 2; i <= N; i++) {
    dp[i] = dp[i - 1] + list[i - 1]; // list는 0번 인덱스부터 저장되어 있으므로 -1 해서 접근
}

 

(2) i부터 j까지의 합을 구한다.

- `i부터 j까지의 합` = `0부터 j까지의 합` - `0부터 i-1까지의 합` 

- 자바스크립트에서 console.log 하는데 시간이 많이 소요되어서, 답을 저장했다가 마지막에 한번에 출력해야 한다.

(각각 출력하려고 하면 시간 초과가 발생한다.)

let answer = "";
intervals.forEach(([i, j]) => {
    answer += `${dp[j] - dp[i - 1]}\n`;
});

console.log(answer);

 

✅ 성공