[백준 13422] 도둑 (C++)

문제 링크: www.acmicpc.net/problem/13422

13422번: 도둑

1. 주의할 점

- N과 M이 같을때의 조건을 잘 세운다

- 최대 몇개를 확인하면 되는지 식을 잘 세운다

- While문 안에 For문을 이용하여 Sum을 계산하지 않는다 -> 두 포인터를 활용한다

 

2. 구현

- 입력받을 배열의 크기를 2배로 하여 N + M -1개의 배열에서 연속된 M개씩 고르도록 한다

- While문을 몇번 반복할것인지 Len을 구해야 한다. Len : 기존배열에서 한바퀴 더 돌아서 계산할 횟수

- 여기선 M = con으로 뒀으며, N = M이라면 추가로 0번, 같지 않다면 M-1번만 확인하면 된다

 

[설명]

N=4 그리고 1,2,3,4를 입력 받는다고 가정

Len식의 이유 1) M=2일 때

1	2	3	4	1(맨 앞의 1)
O	O
	O	O
		O	O
			O	O

=> 4번 확인

Len식의 이유 2) M=4일 때

1	2	3	4
O	O	O	O

 

 

#include <iostream>
using namespace std;
long long money[200000];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, l, r, num, con, k, val, result, len;
	long long sum;
	cin >> test;
	for (int t = 1; t <= test; t++) {
		cin >> num >> con >> k;
		//초기화
		sum = 0;
		result = l = 0;
		r = con - 1;
		len = (con == num) ? 0 : con - 1;

		for (int i = 0; i < num; i++) {
			cin >> val;
			money[i] = val;
			if (i < con) sum += val;
			if (i < len) money[i + num] = val;		
		}
		while (r < num + len) {
			if (sum < k) result++;
			r++;
			sum += money[r];
			sum -= money[l];
			l++;
		}
		cout << result << '\n';
	}
	return 0;
}