BOJ : 2559 수열 (JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log

let inputs = input[0].split(' ').map(Number)
n = inputs[0]
m = inputs[1]

let lst = input[1].split(' ').map(Number)

let prefix_sum = [0]


let temp = 0 
for(let i = 0 ; i < n ; i++){
    
    temp += lst[i]
    prefix_sum.push(temp)
    temp = prefix_sum[i+1] 
}

let maxNum = -10000001

for(let i = m ; i < n+1 ; i++){
    maxNum = Math.max(maxNum , prefix_sum[i] - prefix_sum[i-m])
}

c(maxNum)

 

풀이

누적합을 이용하는 문제이다. 

 

누적합을 구하고 난 후 m일 연속 합이 제일 큰 숫자를 구해야 하는데 이를 구하기 위해선 2일, 3일 , ... , 5일 등등 연속해서 구하는 법을 알아야한다.

 

m=5 라고 가정했을때 , 

prefix_sum[i] - prefix_sum[i-m] 이라는 공식을 구할 수 있었다.

 

예시)

(3 -2 -4 -6 + 0 +3 +7 +13 + 8) - (3 -2 -4 -6 -0)

 

문제

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

2559번: 수열