백준 1806 c++ "부분합" -PlusUltraCode-

https://www.acmicpc.net/problem/1806

 

[필자 사고]

투포인터 알고리즘을 이용하여 푸는 문제이다.

 

문제에서 주어진 조건중 조심해야 될 것은 아래와 같다.

 

S의 범위가 1억이라는 점이다.

브루스트 알고리즘을 이용하면 시간초과를 보게 될 것이다.

또한 자료형 int 가아닌 long을 사용해야 된다.

 

sum을 기준으로 S보다 작으면 endIdx를 키우고
그렇지않으면 startIdx를 이동시키는 방식으로 코드를 구현했따.

 

아래는 코드 해설이다

 

1. 전역 변수 및 배열 정의
   코드에서는 Arr라는 벡터를 통해 각 구간(또는 노드)의 값을 저장하고, N은 배열(또는 그래프)의 크기, S는 목표로 하는 합의 최소값을 나타낸다. Input 함수는 사용자 입력을 통해 배열의 값과 필요한 변수들을 초기화한다.

2. 두 개의 포인터를 이용한 탐색 방식 (Two_Pointer 함수)
두 개의 포인터를 활용해 최단 구간의 길이를 찾는 방식이다.

• 탐색의 출발점
  시작 지점(startIdx)과 끝 지점(endIdx)이 모두 배열의 첫 번째 인덱스에서 시작한다. 초기 합(sum)은 첫 번째 요소로 설정한다.
• 목표를 만족하는 구간 탐색
  두 포인터는 다음과 같은 규칙으로 움직인다:
  • sum >= S인 경우, 현재 구간의 길이(끝 지점과 시작 지점의 차)를 계산하고, 이를 최솟값(result)으로 업데이트한다.
  • 그렇지 않으면, 끝 지점(endIdx)을 늘려 구간을 확장하고 합(sum)을 업데이트한다.
• 구간 최적화
  합이 S 이상인 상태에서 구간 길이를 줄이기 위해 시작 지점(startIdx)을 증가시키고, 이와 함께 합(sum)에서 해당 구간의 값을 빼준다.
• 탐색 종료
  두 포인터를 이동시키며 모든 가능한 구간을 탐색한 후, result를 반환한다. 만약 목표를 만족하는 구간이 없었다면 INT_MAX 값을 반환한다.

3. 게임의 시작 (GameStart 함수)
GameStart 함수는 Two_Pointer를 호출하여 최단 구간 길이를 구한다.

• 만약 반환된 값이 INT_MAX라면, 이는 목표를 만족하는 구간이 없음을 의미하므로 0을 출력한다.
• 그렇지 않다면 최단 구간의 길이를 출력한다.

4. 코드의 전체 흐름

1. 입력값으로 배열의 크기(N), 목표 합(S), 배열 요소들을 초기화한다.
2. Two_Pointer를 통해 목표를 만족하는 가장 짧은 구간을 탐색한다.
3. 탐색 결과에 따라 목표를 만족하는 구간의 길이를 출력하거나 0을 출력한다.

 

[필자 코드]

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<long> Arr;
long N, S;

void Input() {
	cin >> N >> S;

	Arr.resize(N+1);
	for (int i = 0; i < N; i++) {
		cin >> Arr[i];
	}
}

int Two_Pointer() {
	int startIdx = 0;
	int endIdx = 0;
	long sum = Arr[0];
	int result = INT_MAX;
	
	while (startIdx <= endIdx && endIdx < N) {
		if (sum >= S) result = min(result, endIdx - startIdx + 1);

		if (sum < S) {
			
			
				endIdx++;
				sum += Arr[endIdx];
			

		}
		else {
			sum -= Arr[startIdx];
			startIdx++;
		}
		
	}
	return result;
}


void GameStart() {
	int result = Two_Pointer();
	if (result == INT_MAX)cout << 0;
	else cout << result;
	

}

int main(void) {
	Input();
	GameStart();
}