BOJ 27496 - 발머의 피크 이론 링크
(2023.08.14 기준 S3)

문제

남은 시간 N, 섭취한 알코올의 지속시간 L이 주어지고, 매 시간마다 술을 섭취할 것이며 매 시간마다 각 술의 알코올의 양 ai가 N개 주어진다.
술에 포함된 알코올의 양이 A라고 하면 술을 마실 때마다 혈중 알코올 농도 증가량은 A × 0.001로 계산한다면, 혈중 알코올 농도를 0.129와 0.138 사이로 유지한 시간 출력

알고리즘

슬라이딩 윈도우

풀이

지속시간은 L이므로 결국은 구간의 길이가 L인 모든 구간 중 구간합이 129 이상 138 이하인 구간의 개수를 출력하면 된다.
그리고 아직 L개의 술을 마시지 못했을 때도 혈중 알코올 농도를 체크해주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

bool check(int C){ // 혈중 알코올 농도가 0.129 이상 0.138 이하인지 확인
    return 129 <= C && C <= 138;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, L; cin >> N >> L;
    int a[N]; for (int i = 0; i < N; i++) cin >> a[i];

    int result = 0; // 혈중 알코올 농도를 0.129 이상 0.138 이하로 유지한 시간

    // [0, 0], [0, 1], ..., [0, L - 1] 구간 확인
    int C = 0;
    for (int i = 0; i < L; i++){
        C += a[i];
        result += check(C);
    }

    // [1, L], [2, L + 1], ..., [N - L, N - 1] 구간 확인
    for (int i = L; i < N; i++){
        C += a[i];
        C -= a[i - L];
        result += check(C);
    }

    cout << result;
}

• Python

import sys; input = sys.stdin.readline

def check(C): # 혈중 알코올 농도가 0.129 이상 0.138 이하인지 확인
    return 129 <= C <= 138

N, L = map(int, input().split())
a = list(map(int, input().split()))

result = 0 # 혈중 알코올 농도를 0.129 이상 0.138 이하로 유지한 시간

# [0, 0], [0, 1], ..., [0, L - 1] 구간 확인
C = 0
for i in range(L):
    C += a[i]
    result += check(C)

# [1, L], [2, L + 1], ..., [N - L, N - 1] 구간 확인
for i in range(L, N):
    C += a[i]
    C -= a[i - L]
    result += check(C)

print(result)