백준/ Silver 5 문제 , 백준 Node.js 자바스크립트 14929 , 귀찮아 (SIB)

백준/ Silver 5 문제 , 백준 Node.js 자바스크립트 14929 , 귀찮아 (SIB) 

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


덧붙일 말 🏷️
문제 설명이 너무 대충이라 처음에 무슨 문제이지 싶었다.

 

 

 

문제 출처 🏠

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

14929번: 귀찮아 (SIB)

 

 

 

요구사항 📋

1. 첫째줄에 n 이 주어진다.

2. 두번째 줄에 n개의 숫자들이 주어진다.

3. 나올 수 있는 두 숫자 곱 경우의 수들의 합을 구하여라.  

 

 

해결 전략 📝

 

1. 배열의 크기를 줄여가면서 각각 합을 계속 구해주면 메모리초과, 시간초과 가 발생한다.

 

2. 누적합을 이용하자

 

처음에 주어진 숫자들의 모든 합을 구한다.

 

이후, 0번 인덱스부터 시작해서 N-2 번인덱스까지 for문으로 순회하는데,

 

0번 인덱스의 값을 누적합에서 빼준 뒤, 이 값과 누적합의 값을 곱해준다.

 

이는 1번인덱스부터 N-1번 인덱스 값에 각각 0번인덱스를 곱해서 더한 값이랑 같기 때문이다.

 

나온 결과 값을 결과값을 저장하는 변수에 더해준다.

 

이후 인덱스를 증가시켜 1번인덱스값을 누적합에서 빼준 뒤 위와 같은 작업을 반복한다.

 

이 과정을 N-2번 인덱스까지 반복하면 한번의 누적합 계산만으로 모든 경우의 수들을 구할 수 있다.

 

 

 

 

 

정답 💯

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const [N, ...Nums] = input;
Nums.map((num) => Number(num));
function solution(n, nums) {
  let result = 0;
  let sum = nums.reduce((pre, cur) => pre + cur);
  for (let i = 0; i < n - 1; i++) {
    let v = nums[i];
    sum -= v;
    result += sum * v;
  }
  return result;
}
console.log(solution(N, Nums[0]));

 

 

 

 

 

느낀점 🧑‍💻

- 누적 합을 계속적으로 계산해야 하는 과정이 있다면, 이 과정을 최대한 줄일 수 있는 법을 이용하자.