BOJ 13422 : 도둑

• 문제 링크 : boj.kr/13422
• 난이도 : G4
• 태그 : 누적합, 두 포인터

13422번: 도둑

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int T;
    cin >> T;
    while(T--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<ll> arr(n*2 + 1);
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
            arr[i+n] = arr[i];
        }
        for(int i = 1; i < 2*n+1; i++) {
            arr[i] += arr[i-1];
        }
        if(n == m) {
            cout << (arr[m]-arr[0] < k ? 1 : 0) << "\n";
            continue;
        }
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i+m]-arr[i] < k) cnt++;
        }
        cout << cnt << "\n";
    }

    return 0;
}

---

풀이

누적합을 이용해서 답을 구해준다. 원순열이기 때문에 기존의 배열을 한번 더 반복하여 처리해준다.

여기서 유의할 점은, n=m일때 회전하더라도 경우가 달라지지 않으므로 예외처리를 해주어야 한다.