[백준] 합 구하기 (javascript)

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

11441번: 합 구하기

 

🤔 해결방법

1. 0인 요소가 n+1개인 배열을 만들고 누적 합산 숫자를 해당 인덱스에 넣어준다

2. 끝지점 요소에서 시작요소-1 까지 뺀 값을 차례로 개행하여 출력한다

 

 

🔑 풀이

문제를 읽자마자 바로 구간의 합을 하나씩 더해주도록 풀었다.

역시나 호락호락하지 않은 백준은 시간초과를 뱉어냈다.😥

const input = require("fs")
    // .readFileSync("/dev/stdin")
    .readFileSync(__dirname + "/input.txt")
    .toString()
    .trim()
    .split("\n");
  const [...numbers] = input[1].split(" ").map(Number);

  let range = [];
  let answer = "";

  for (let i = 3; i < 3 + Number(input[2]); i++) {
    range.push(input[i].split(" ").map(Number));
  }

  for (i = 0; i < range.length; i++) {
    let sum = 0;
    for (j = range[i][0] - 1; j <= range[i][1] - 1; j++) {
      sum += numbers[j];
    }
    answer += sum + "\n";
  }
  console.log(answer);

 

구글링해보니 누적 합으로 풀어야 시간초과가 안난다는 것을 알 수 있었다.

0인 요소가 n+1개인 배열을 만들어 누적 합산 숫자를 해당 인덱스에 넣어주고

i부터 j까지 구간의 합 = j까지의 합 - (i-1)까지의 합임을 이용해 푸는 문제였다.

누적 합을 이용한 코드는 다음과 같다.

const input = require("fs")
    .readFileSync("/dev/stdin")
    //.readFileSync(__dirname + "/input.txt")
    .toString()
    .trim()
    .split("\n");
  const [...numbers] = input[1].split(" ").map(Number);

  let range = [];
  let answer = "";

  for (let i = 3; i < 3 + Number(input[2]); i++) {
    range.push(input[i].split(" ").map(Number));
  }

  // 누적 합 배열
  let sumArray = new Array(numbers.length).fill(0);
  sumArray[0] = numbers[0];
  for (let i = 1; i < numbers.length; i++) {
    sumArray[i] = sumArray[i - 1] + numbers[i];
  }

  for (i = 0; i < range.length; i++) {
    let sum = 0;
    let start = range[i][0] - 1;
    let end = range[i][1] - 1;

    if (start === 0) {
      answer += sumArray[end] + "\n";
    } else {
      answer += sumArray[end] - sumArray[start - 1] + "\n";
    }
  }
  console.log(answer);