C++ / 백준 / 13422 / 도둑

문제

 

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

13422번: 도둑

 

 

문제풀이

 

누적합, 슬라이딩 윈도우 문제이다.

집을 고를 때는 항상 연속된 위치에 있는 집만 고를 수 있다.

붙어있는 m개 만큼의 집을 고르고 돈의 총합을 구해 K보다 작으면 개수를 하나 늘려주면 된다.

 

		for (int idx = 0; idx < M; ++idx) sum += money[idx];		

		if (sum < K) ++answer;

		for (int idx = 1; idx < N; ++idx) {
			sum -= money[idx - 1];
			sum += money[(idx + M - 1) % N];
			if (idx - 1 == (idx + M - 1) % N) break;
			if (sum < K) ++answer;
		}

처음에 0번 위치부터 M-1까지의 돈의 총합을 sum에 저장하고, K보다 작으면 answer에 1을 더한다.

 

그다음에는 idx=1부터 N-1까지 반복한다.

idx-1 위치에 해당하는 집의 돈을 뺀다고 생각하면 된다.

한 집의 돈을 뺐으니 뒤에 있는 집의 돈을 더해야 한다.

집들은 원형으로 이어져있으므로 인덱스가 벡터의 범위를 넘어가는 것을 방지하기 위해 나머지 연산을 통해 다음 집의 위치를 구한다.

만약 뺀 집과 더한 집이 같다면 N==M인 경우이므로 이 경우에는 위에서 이미 구했으므로 break를 통해 반복문을 종료하면 된다.

 

해당 반복문이 종료되면 answer을 출력한다.

 

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int T(0);
	cin >> T;
	for (int test_case = 1; test_case <= T; ++test_case) {
		int N(0), M(0), K(0);
		cin >> N >> M >> K;
		vector<int>money(N, 0);
		int sum(0), answer(0);

		for (int idx = 0; idx < N; ++idx) cin >> money[idx];		

		for (int idx = 0; idx < M; ++idx) sum += money[idx];		

		if (sum < K) ++answer;

		for (int idx = 1; idx < N; ++idx) {
			sum -= money[idx - 1];
			sum += money[(idx + M - 1) % N];
			if (idx - 1 == (idx + M - 1) % N) break;
			if (sum < K) ++answer;
		}
		cout << answer << '\n';
	}
}