백준 13422 도둑 (c++) : 피너클

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

13422번: 도둑

투 포인터 문제다.

예제를 예로 들어 설명하겠다. 현재 n은 8, m은 3, k는 15이다.

3

4

7

5

6

4

2

9

시작은 0, 마지막은 m-1인 합을 만든다.

3

4

7

5

6

4

2

9

현재 합은 3 + 4 + 7해서 14다. k보다 작으니 ans++를 해준다. 그후 시작을 1, 마지막을 m으로 해준다.

3

4

7

5

6

4

2

9

현재 합은 4 + 7 + 5해서 16이다. k보다 크니 넘어간다.

이 과정을 계속해서 반복해 답을 구하는 것이다.

중요한건 합을 구할때 4 + 7 + 5를 하는 것이 아닌 그전 합인 14에서 3을 빼고 5를 더하는 것이다.

이 과정을 end가 m-1이 될때 까지 반복한다.

3

4

7

5

6

4

2

9

만약 현재 end가 n-1이라면 다음에는 end를 0으로 바꿔줘야한다.

3

4

7

5

6

4

2

9

 

int test;
cin >> test;
while (test-- > 0) {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) cin >> arr[i];
	int ans = 0;
	int sum = 0, start = 0, end = m - 1;
	for (int i = 0; i < m; i++) sum += arr[i];

기본적인 준비를 한다.

ans는 답, sum은 현재 합, start와 end는 위에 나온 설명과 같다.

sum에는 미리 0부터 m-1까지의 합을 구한다.

if (n == m) { 
	cout << (sum < k ? 1 : 0) << endl; 
	continue;
}

만약 n과 m이 같다면 한번만 검사하면 된다. sum과 k를 비교해 바로 출력하고 뒤의 내용을 무시한다.

while (true) {
	if (sum < k) ans++;

같지 않다면 while을 실행하고 만약 현재 합이 k보다 작다며 ans++를한다.

	sum -= arr[start];
	start++;
	end++;
	if (end >= n) end = 0;
	if (end == m - 1) break;
	sum += arr[end];

그리고 현재 sum에서 arr[start]값을 빼고 start++를 한다.

그후 end++를 한뒤 만약 end가 n과 같거나 크다면 0으로 바꾼다.

만약 end가 m-1이라면 한바퀴를 다 돌았다는 것이니 while문에서 빠져나간다.

그후 sum에 arr[end]를 추가한다.

cout << ans << endl;

whlie문을 빠져나가면 ans를 출력한다.

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, k;
int arr[100001];

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

	int test;
	cin >> test;
	while (test-- > 0) {
		cin >> n >> m >> k;
		for (int i = 0; i < n; i++) cin >> arr[i];

		int ans = 0;
		int sum = 0, start = 0, end = m - 1;
		for (int i = 0; i < m; i++) sum += arr[i];
		if (n == m) { 
			cout << (sum < k ? 1 : 0) << endl; 
			continue;
		}
		while (true) {
			if (sum < k) ans++;
			sum -= arr[start];
			start++;
			end++;
			if (end >= n) end = 0;
			if (end == m - 1) break;
			sum += arr[end];
		}
		cout << ans << endl;
	}
}

전체코드다.