[백준 10986] 나머지 합 - javascript,node.js,구간합,누적합

문제링크 : https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

알고리즘 :

1. n개의 수를 누적합을 저장한다.

2. 아래 구간합의 나머지 수학 공식을 알아야 한다.

- 즉 총합의 나머지가 0과 같아야 한다 했으니 결국 좌변의 합에 % m을 한 것과 우번의 합에 % m을 한것이 같아야 한다.

3. 조합을 이용한다. 즉 다른 n개 중 순서 상관없이 r개를 뽑는다.

n!/(n-r)!r!

 

즉 하나의 식으로 생각하면

psum     : [ 1, 3, 6, 7, 9 ]
psum % m : [ 1, 0, 0, 1, 0 ]

0이 3개, 1이 2개이다.
즉 정답이 되는 경우의 수는  
0인 psum 3개 + (0의 개수=3)*(3-1)/2 + (1의 개수=2)*(2-1)/2 이다.

 

문제풀이 : 

1. 누적합을 구해준다.

const [n,m] = input[0].split(' ').map(Number)
const arr = input[1].split(' ').map(Number)
let answer = 0;
const psum = new Array(n+1).fill(0)

arr.forEach((v,i)=>{
  psum[i+1] = psum[i] + v

})

for(let i=1;i<psum.length;i++){
  let sum = psum[i];
  if(sum%m===0) answer++;
  if((sum-psum[i-1])%m===0){
    answer++
  }
}

2. 누적합을 m으로 나눈 수로 index 0을 제외한 값을 map으로 저장한다.

이때 키는 나머지 값, value는 개수이다.

const map = new Map();

psum.slice(1).forEach(v=>{
  map.set(v%m,(map.get(v%m)||0)+1)
})

 

3. map을 for문 돌려서 각각의 식을 구해 더해준다.

const check = [...map]
check.forEach(v=>{
  answer+=(v[1]*(v[1]-1))/2
})

4. 0의 개수를 더해주고 출력한다.

answer+=map.get(0)||0

5. 최종 코드

const filePath = require('path').join(__dirname, '/test.txt');
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');


// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')

const [n,m] = input[0].split(' ').map(Number)
const arr = input[1].split(' ').map(Number)
let answer = 0;
const psum = new Array(n+1).fill(0)

arr.forEach((v,i)=>{
  psum[i+1] = psum[i] + v

})

// console.log(psum)

const map = new Map();

psum.slice(1).forEach(v=>{
  map.set(v%m,(map.get(v%m)||0)+1)
})
// console.log(map)
const check = [...map]
check.forEach(v=>{
  answer+=(v[1]*(v[1]-1))/2
})



answer+=map.get(0)||0
console.log(answer)