백준 1806_부분합(C++)

 

www.acmicpc.net/problem/1806

1806번: 부분합

[문제 풀이]

투 포인터를 이용하여 문제를 풀었습니다.

 

이 문제는 입력으로 들어온 수열의 부분집합의 합이 S 이상이 되는 것 중, 가장 짧은 수열을 찾는 문제입니다. 전형적인 투 포인터 문제입니다. 

 

코드 설명

• 투 포인터를 위해 pre_idx와 post_idx를 0으로 초기화 합니다.
• sum의 값을 배열 첫 번째 값으로 초기화 합니다.
• 초기화 해준 sum의 값이 S와 같으면 값 1을 출력 합니다. 아닌 경우 while문을 통해 세 가지의 경우로 분리해 answer를 구해줍니다.
• sum이 같은 경우, 길이가 1이라면 값 1을 출력 합니다. 아닌 경우, 값을 비교하고 post_idx 값을 증가시켜주고 arr[post_idx]를 sum에 추가합니다.
• sum이 S보다 큰 경우, 길이가 1이라면 값 1을 출력시켜줍니다. 아닌 경우 arr[pre_idx]를 sum에서 빼주고 pre_idx 값을 증가 힙니다. 또한, pre_idx가 post_idx를 넘어버린다면 초기화 합니다.
• sum이 S보다 작은경우, post_idx를 증가시켜주고 post_idx가 N보다 크거나 같으면 break 합니다.

[코드]

#include<iostream>

using namespace std;

int N, S, answer = 987654321;

int arr[100001];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> S;

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int pre_idx = 0;
	int post_idx = 0;

	int sum = arr[0];

	if (sum == S) {
		cout << 1 << endl;
		return 0;
	}

	while (post_idx < N && pre_idx <= post_idx) {

		if (sum == S) {
			
			int length = post_idx - pre_idx + 1;
			if (length  == 1) {
				cout << 1 << endl;
				return 0;
			}

			if (answer > length)
				answer = length;

			post_idx++;
			sum += arr[post_idx];

				

		}
		else if (sum > S) {

			int length = post_idx - pre_idx + 1;
			if (length == 1) {
				cout << 1 << endl;
				return 0;
			}

			if (answer > length)
				answer = length;

			sum -= arr[pre_idx];
			pre_idx++;

			if (pre_idx > post_idx && pre_idx < N) {
				post_idx = pre_idx;
				sum = arr[pre_idx];
			}

		}
		else if (sum < S) {

			post_idx++;

			if (post_idx >= N)
				break;

			sum += arr[post_idx];

		}
	}


	if (answer == 987654321)
		answer = 0;
	cout << answer << endl;

	return 0;

}