백준 - 1806 부분합

접근방식

문제를 보면 N의 값이 100,000 이 주어진다. 대부분 100,000개면 시간복잡도 계산을 요구하는 경우가 많은데, 

해당 경우에는 이중 포문을 돌리면 무조건 시간초과가 발생하게 된다.

그래서 어떻게 하면 for 문 한번에 해결할까에 대해 고민 후 2003번 수들의 합2에서 마지막에 남겨 두었던 투 포인터 방법을 이용하기로 했다. 

 

해당 문제는 생각보다 오래걸렸는데 그 이유는 문제를 잘 못 이해했었다. 

S의 값과 동일한 경우만 인줄 알았는데 S의 값 이상인 경우 였으니까 조심하자.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 210000000
using namespace std;

int main() {

	int n;
	int s;

	cin >> n;
	cin >> s;

	int arr[100001];

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x; 

		arr[i] = x;
	}
	
	int head = 0;
	int tail = 0;
	int sum = 0;
	int len = 0;
	int result = INF;

	while (true) {


		if (head == n - 1 && head == tail) {
			break;
		}

		if (s > sum) {
			if (head > n - 1) {
				break;
			}

			sum = sum + arr[head];
			head++;
			len++;
		}

		else {
			if (result > len) {
				result = len;
			}
			sum = sum - arr[tail];
			tail++;
			len--;
		}
	}

	if (result == INF) {
		result = 0;
	}

	cout << result;
	return 0;
}

풀이 방법

투포인터 방법은 

head 값과 tail 값을 선언해준다. 

head와 tail이 의미하는바는 배열의 인덱스를 나타낸다. 

 

예를 들어 

N = 5, S = 0 이고

배열의 값은 0 , 1, 1, 1, 1 이라고 가정해보자

 

아래는 배열에 값을 넣어준 상태이다.

0

1

1

1

1

head와 tail의 시작은 0이고 arr[head] / arr[tail] 의 값은 0이다.

이때 순차적으로 head의값을 증가시키면서 부분합(sum) 에 값을 누적시켜준다. 

코드에서 보면 sum = sum + arr[head] / head++ 를 반복하고 있는 부분이다.

 

전체적인 코드를 보면

s의 값이 부분합의 값 보다 큰 경우는 head의 값을 증가시켜주면서 len의 길이도 증가시켜준다

반대로 부분합의 값이 크거나 같은 경우 head의 값은 멈춘 상태로 tail의 값을 올려주고, len의 길이를 감소시켜준다. 

그러면서 sum = sum - arr[tail] 로 부분합의 값을 줄여 주면서 s의 값과 비교하고 len의 가장 최소 길이를 출력해주는 방식이다.