[백준] 1806번: 부분합 C++로 풀어보기

1806번 설명

생각

투 포인터를 사용해서 풀 수 있다.
st, en 두 포인터를 둔다.

 

1. 수들을 입력받아 배열에 저장한다.

2. 수의 합을 저장하는 변수 total은 arr[0]을 더 해주고, 줄의 길이를 저장하는 변수 len은 최대한 큰 수로 둔다(0x7fffffff).

3. en을 0으로 둔다.

4. en이 n보다 작고 total이 s보다 작다면 en을 한 칸 오른쪽으로 옮긴다.

5. 그러고도 en이 n보다 작다면 total에 arr[en]을 더 해준다.

6. 계속 더하다보면 total이 s보다 커진다.

7. 그러면 그 때 en-st+1이 len보다 작다면 len에 en-st+1을 저장한다.

8. st가 다음 칸으로 넘어가기 전에 total에서 arr[st]를 빼준다.

9. 만약 s보다 큰 부분합을 찾지 못했다면 0을 출력하고, 아니라면 len을 출력한다.

 

코드

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

int arr[100005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, s;
	cin >> n >> s;
	
	for (int i = 0; i < n; i++) { // 입력
		cin >> arr[i];
	}

	int en = 0; 
	int len = 0x7fffffff; // 줄의 길이를 저장하는 변수
	int total = arr[0]; // 수의 합을 저장하는 변수 
	for (int st = 0; st < n; st++) {
		while (en < n && total < s) {
			en++; // en을 한 칸 오른쪽 옆으로 옮긴다
			if (en != n) {
				total += arr[en]; // arr[en]을 total에 더해준다
			}
		}

		if (en == n) { // 범위를 벗어나면 
			break;
		}

		
		if (total >= s) { // total이 s보다 크다면
			if (en - st + 1 < len) { // 
				len = en - st + 1;
			}
		}

		total -= arr[st]; // st가 다음으로 넘어가기 전에 total에서 arr[st]를 뻬준다.
	}

	if (len == 0x7fffffff) { // s보다 큰 부분합을 찾지 못했다면
		len = 0; // len에 0을 저장한다.
	}
	cout << len; // len 출력
}

예외처리가 중요했다. en이 n이 아닐 때 arr[en]을 total에 더해주는 부분이나, len이 0x7fffffff라면 len에 0을 저장하는 부분이 있어야 문제를 해결할 수 있다. 꼼꼼히 따져보는 습관을 들이자.

 

결과

1806번 결과