백준 1806 부분합 C++ 풀이

해당 리스트의 연속 수열의 합이 특정 값보다 이상이 되는 것 중 가장 짧은 것의 길이를 확인하는 문제이다. 

https://butter-shower.tistory.com/226 

[Algorithm] 투포인터(Two Pointer) 알고리즘

투포인터 알고리즘은 병합정렬에서 사용한 Conquer 방식과 유사하게 start와 end 지점에서의 부분합을 계산하는 알고리즘이다.

이 문제에서는 특정값 S의 이상이 되는 값들 중 가장 짧은 것을 구하라고 하였으니, 아래의 방법들로 소스코드를 구현한다. 

(1) for문에서 start 변수를 기준으로 while 내부에서 end 값을 늘려주며 부분합을 계산한다. 
(2) 부분합이 S 이상이 되는 경우에 기존에 구하였던 min 변수보다 작은 경우 min을 갱신하여준다.
(3) 부분합의 계산이 끝났을 때 다음 스텝으로 넘어가 부분합을 새롭게 계산해주기 위해 현재 start 위치의 값을 빼준다.

 

소스 코드

#include <iostream>
#define MAX 100000
using namespace std;

int main() {
	int n; // 수열의 길이
	int s; // 최소 숫자
	cin >> n >> s;
	int arr[MAX]; // 수열을 담을 배열
	for (int i = 0; i < n; i++) {
		cin >> arr[i]; 
	}

	int count = 0;
	int sum = 0; // 현재 간격의 값들을 더한 값
	int end = 0;
	int min = 0; // 최솟값을 저장할 변수

	for (int start = 0; start < n; start++) {
		while (sum < s && end < n) { // 현재 부분합이 s보다 작고, 마지막 지점에 도달하지 않았으면
			sum += arr[end];
			end++;
		}
		if (sum >= s) { // 부분합이 s 이상인 경우
			if (start == 0)
				min = end - start;
			else {
				if (end - start < min)
					min = end - start;
			}
		}
		sum -= arr[start]; // 다음 위치를 탐색하기 위해 부분합에서 현재 위치의 값을 빼준다.
	}
	
	cout << min << endl;
	return 0; 
}

 

+) 출력 조건에  "만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다." 라고 나와있어서, min의 초기값을 0으로 설정해주지 않으면 런타임에러가 뜬다.