문제

문제 링크

문제 접근

  • 이 문제는 큐를 이용해서 해결할 수 있다.
  • 차선을 큐라고 생각하고 하나씩 제거하고 추가하기를 반복한다.
  • 이때 만약 새로운 원소의 무게를 감당할 수 없을 때는 들어올 수 있을 때까지 0을 넣어준다.
  • 이를 반복하면서 cnt를 확인한다.

코드

#include <cstdio>
#include <queue>
using namespace std;
int n, w, l, a[1001], ans;
int main(){
    scanf("%d %d %d", &n, &w, &l);
    for(int i = 0; i < n; i++)scanf("%d", &a[i]);
    queue<int> q;
    int sum = 0;
    for(int i = 0; i < n; i++){
        while(1){ 
            if(q.size() == w){
                sum -= q.front();
                q.pop();
            }
            if(sum + a[i] <= l) break;
            q.push(0);
            ans ++;
        }
        q.push(a[i]);
        sum += a[i];
        ans ++;
    }
    ans += w;
    printf("%d", ans); 
}

느낀점

  • 큐가 바로 떠올라서 다행이었다. 다른 문제도 이렇게 접근 방법이 술술 떠올랐으면 좋겠다..ㅠ