[백준] 발머의 피크 이론 (JS)

문제

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

발머의 피크 이론이란 혈중 알코올 농도 C가 (0.129≤C≤0.138)일때 초인적인 프로그래밍 능력을 가지게 된다는 이론이다. 기령이는 발머의 피크 이론 신봉자이기 때문에 지금부터 코딩테스트를 볼 때까지 혈중 알코올 농도를 최대한 지키려고 한다. 기령이는 매 시간마다 정해진 술을 섭취하며, 섭취한 알코올은 일정 시간이 지나면 분해된다. 기령이가 지금부터 코딩테스트를 볼 때까지 얼마나 혈중 알코올 농도를 0.129와 0.138 사이로 지킬 수 있는지 알아내보자. 단, 혈중 알코올 농도 증가량은 술에 포함된 알코올의 양 A×0.001로 계산하며 최초의 혈중 알코올 농도는 0이다.

입력

첫째 줄에 코딩테스트를 볼 때까지 남은 시간 N(1≤N≤1 000 000), 섭취한 알코올의 지속시간 L(1≤L≤10 000,L≤N)이 공백으로 구분되어 주어진다.

둘째 줄에 술에 포함된 알코올의 양 정수 ai(0≤ai≤200)가 공백으로 구분되어 주어진다.

출력

혈중 알코올 농도 C를 (0.129≤C≤0.138)로 유지한 시간을 출력한다.

풀이

1. 이 문제의 핵심은 윈도우 크기를 처음부터 고정하지 않는 것이다.
2. l초까지는 윈도우의 크기를 유동적으로 증가시키며 알콜 농도 C가 (0.129 ≤ C ≤ 0.138) 범위에 있는 시간을 구한다.
3. 윈도우 크기가 l에 도달한 후부터는 맨 왼쪽 값을 제거하고 오른쪽 값을 추가하여, 알콜 농도 C가 (0.129 ≤ C ≤ 0.138) 범위에 있는 시간을 구한다.

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

const [n, l] = input[0].split(" ").map(Number);
const arr = input[1].split(" ").map(Number);

let answer = 0;
let windowSum = 0;

for (let i = 0; i < l; i++) {
    windowSum += arr[i];    
    if (129 <= windowSum && windowSum <= 138) {
        answer++;
    }
}

for (let i = l; i < n; i++) {
    windowSum = windowSum - arr[i - l] + arr[i];
    if (129 <= windowSum && windowSum <= 138) {
        answer++;
    }
}

console.log(answer);

결론

처음에는 "개수"를 기준으로 고정된 슬라이딩 윈도우를 사용했는데, 이 방식에서 오류가 발생했다.

실제로는 개수를 고정시키기 전에, 먼저 시간 차가 L 이하인 경우도 고려해야 했다.