[Algorithm]Baekjoon 13422번 :: 도둑

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
int t, n, m, k;
int arr[100001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    while (t--)
    {
        cin >> n >> m >> k;
 
        for (int i = 0; i < n; ++i)
        {
            cin >> arr[i];
        }
 
        long long sum = 0;
 
        for (int i = 0; i < m; ++i)
        {
            sum += arr[i];
        }
 
        int answer = 0;
        if (sum < k) ++answer;
 
        if (n == m)
        {
            printf("%d\n", answer);
            continue;
        }
 
        for (int i = 0; i < n-1; ++i)
        {
            sum -= arr[i]; // 스타트 빼고
            sum += arr[(i + m) % n]; // 다음꺼 더하기
 
            if (sum < k) ++answer;
        }
 
        printf("%d\n", answer);
    }
}
 
 

 

현재 구간이 조건에 맞을경우, 즉 구간의 합들이 k 미만일 경우 정답을 카운팅해주면 되는데, 

처음에 구간 맞춰야해서 미리 한번 검사를 했다. 그렇기 때문에 이후 반복문으로 검사할 때는 한번 빼줘야한다 (53번째 라인 n-1)

 

거기에 더해서, n값이랑 m값이 같을 경우 연속된경우는 딱 한가지밖에 없으니 이 경우도 예외처리를 잘 해주면 된다.