[G4] 백준 13422번 도둑 C++ 슬라이딩 윈도우

리뷰

 

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

원형 데이터에서 윈도우 내 값의 합이 k이하인 개수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• t : 테스트 케이스의 개수를 저장할 변수
• n : 집의 개수를 저장할 변수
• m : 연속된 집을 참조할 수 있는 횟수를 저장할 변수
• k : 경보가 발령하기 위한 최소값을 저장할 변수
• a : 각 집의 돈의 개수를 저장할 배열

 

함수

없음

 

 

문제풀이

1. t값을 입력 받고, t번의 테스트케이스를 수행한다.
2. 매 테스트 케이스마다 n, m, k에 값을 입력 받고, 변수 total을 0으로 초기화한다.
3. n개의 집의 돈을 입력 받아 a배열을 초기화 하고, total에 각 돈의 수를 저장한다.
4. 기저 조건으로 n, m이 동일할 경우 total이 k미만이면 1을, 아니면 0과 출력 후 개행문자를 삽입, continue처리한다.
5. 변수 sum을 0으로 초기화 하고 0부터 m-1까지의 집의 돈을 sum에 더해준다.
6. 변수 cnt를 sum이 k미만이면 1로, 아니면 0으로 초기화한다.
7. 0부터 n-2까지 순회하며 sum에 a[i]를 빼주고, 변수 f를 i+m이 n이상이면 i+m-n로, 아니면 i+m으로 초기화한다.
8. sum에 a[f]를 더해주고, 갱신된 sum이 k 미만이면 cnt를 증가시킨다.
9. 모든 탐색을 마친 후 cnt에 저장된 값을 출력하고 개행문자를 삽입한다.

 

트러블 슈팅

1. 크기가 m인 윈도우를 원형탐색을 정확하게 수행했으나 88%에서 WA를 받았다.
2. n, m이 동일한 경우 각각의 케이스를 독립적으로 보지 않고 하나의 케이스로 보는 엣지 케이스가 숨어있었다.
3. 따라서 n, m이 동일한 경우 초기 total값과 비교하여 조기종료하는 로직을 삽입하며 AC를 받았다.

 

참고 사항

1. N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ N), K(1 ≤ K ≤ 1,000,000,000), 각 집의 돈의 양은 1이상 10,000이하의 정수
2. 최악의 경우에도 int범위 내에서 처리가 되므로 long long타입 자료형은 고려하지 않아도 된다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e5;
int t, n, m, k;
int a[N];

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

	cin >> t;
	while (t--) {
		cin >> n >> m >> k;
		int total = 0;
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
			total += a[i];
		}

		if (n == m) {
			cout << (total < k ? 1 : 0) << "\n";
			continue;
		}

		int sum = 0;
		for (int i = 0; i < m; ++i) sum += a[i];
		int cnt = sum < k ? 1 : 0;

		for (int i = 0; i < n - 1; ++i) {
			sum -= a[i];
			int f = i + m >= n ? i + m - n : i + m;
			sum += a[f];

			if (sum < k) ++cnt;
		}
		cout << cnt << "\n";
	}
}