백준12847 - 꿀 아르바이트 (누적합) node.js

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

문제 풀이 방식

n의 최댓값이 10만 이하이기 때문에, 최소한의 시간 복잡도로 해결할 수 있는 방식으로 접근했다.

문제 해결 방식은 단순하다. 우리에게 5일의 시간이 주어지고, 2일 간 일을 할 수 있다고 할 때,

미리 처음에서부터 2일차까지의 수익을 구한 뒤, 이 값에서부터 i일차의 수익은 가산, i-2일차의 수익은 감산해가며 전체 값을 갱신하고

이 해당값이 최댓값이라면 최댓값으로 갱신하는 것을 반복하며 최댓값을 구할 수 있었다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const [[n, m], arr] = data.map((el) => el.split(" ").map(Number));

  let max = 0,
    total = 0;

  for (let i = 0; i < m; i++) total += arr[i];
  max = total;

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

  console.log(max);
}

solution(input);