[BOJ/백준][Gold4] 13422 : 도둑 (C++)

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

13422번: 도둑

 

 

[난이도] Gold4
[유형] 구간합

[풀이]
시작점이 0~N-1일때의 모둔 구간합을 구해주면 된다. 시작점을 바꿀때마다 구해줄 필요 없이
시작점이 i인 경우, 시작점이 i-1일때의 구간합에서 a[i-1]의 값을 빼고, a[(i+M-1)%N] 일때의 값만
더해주면 각 시작점마다 O(1)에 구할 수 있으므로 시간내에 해결이 가능하다.

 

#include <cstdio>
int tc,N,M,K,a[100000];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&N,&M,&K);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        int ans=0,sum=0;
        for(int i=0;i<M;i++) sum+=a[i];
        if(sum<K) ans++;
        if(N!=M){
            for(int i=1;i<N;i++){
                sum-=a[i-1];
                sum+=a[(i+M-1)%N];
                if(sum<K) {
                    ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13422.cpp