[1806 번] 부분합

www.acmicpc.net/problem/1806

 

• 투포인터를 이용해서 시간제한 안에 알고리즘을 작동시키는 것이 포인트입니다.

주어진 입력 N은 100,000 보다 작은 수 입니다.

모든 수열을 확인하는 방식은 O(N^2) 의 시간복잡도를 가지게 되는데

이는 문제의 시간제한 0.5초 안에 작동이 불가능합니다.

따라서 투포인터를 이용해서 시간 복잡도를 O(N)으로 구현했습니다.

 

우선 주어지는 N과 S 값, N개의 배열 원소를 입력 받습니다.

	int n, s; cin >> n >> s;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

 

이제 투포인터를 사용한 부분을 보겠습니다.

	int left = 0;
	int right = 0;
	int sum = arr[left];
	int min_length = INT_MAX;

	while (1) {

		if (right == n) break;

		if (sum >= s) {
			min_length = min(min_length, right - left + 1);
			sum -= arr[left++];
		}
		else {
			sum += arr[++right];
		}

	}

• 두 포인터를 각각 left와 right로 선언하면서 0으로 초기화합니다.
• 매 진행 상황에서 left와 right사이의 배열 원소의 합을 저장하기 위한 변수 sum을 선언하면서 배열의 첫번째 원소로 초기화 합니다. (left == 0, right == 0 이기 때문에)
• 제시된 조건(부분배열의 합이 주어진 S 보다 클 때)을 만족할 때 마다 right와 left 사이의 길이를 구해서 최소값을 저장하는 변수 min_length를 선언하면서 INT형의 최대값으로 초기화합니다( <climits>의 INT_MAX 사용 )
• while문 내부에서 우선 종료조건을 설정합니다. right포인터가 n에 다다르면 종료합니다.(모든 부분수열 탐색을 마친경우) 
• sum의 값이 s 보다 큰 경우 (문제 조건을 만족한 경우) 부분 배열 길이의 최솟값 변수 min_length를 갱신하고 left포인터를 오른쪽으로 한 칸 옮깁니다.
• sum의 값이 s 보다 작은 경우 (문제 조건을 만족하지 못한 경우) right포인터를 오른쪽으로 한 칸 옮깁니다.

 

마지막 출력 부분입니다.

	if (min_length == INT_MAX) {
		cout << 0;
	}
	else cout << min_length;

 

주어진 S 보다 큰 배열을 만들 수 없는 경우에 대한 예외처리를 해줍니다.(0 출력)

그 외의 경우에는 계산된 min_length를 출력합니다.