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

문제

1806번: 부분합

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

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

정답 코드

#include <iostream>
using namespace std;
long long input[100001];
long long sum_input[100001];
int main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	int n,m;
	cin >> n >> m;
	int start_idx = -1;
	for (int i = 0; i < n; i++){
		cin >>input[i];
		if (i != 0)
			sum_input[i] = sum_input[i - 1] + input[i];
		else 
			sum_input[i] = input[i];
		if (sum_input[i] >= m && start_idx == -1)
			start_idx = i;
	}
	if (start_idx == -1){
		cout << 0 <<"\n";
		return (0);
	}
	int len = 100001;
	int end = 0;
	for (int start = 0; start < n; start++){
		while(end < n && sum_input[end] - sum_input[start] < m) end++;
		if (end == n){
			if (sum_input[n - 1] == m)
				len = n;
			break;
		}
			
		if (sum_input[end] - sum_input[start] >= m)
			len = min(len, end - start);
	}
if (len == 100001)
		len = 1;
	cout << len << "\n";
}

문제 풀이의 흐름

• 입력을 받으면서 이전 값의 누적합을 더하는 방식으로 먼저 저장합니다.

• 만약 모든 수의 합이 찾으려는 부분 합보다 작다면 불가능하므로 0을 출력하고 종료합니다.

• 이후 투포인터를 사용해서 시작은 0부터 해당 연속된 값이 찾으려는 값보다 작다면 끝부분 포인터를 증가시킵니다.

• 만약 넘었다면 그값이 최소값인지 확인 후 다시 end를 증가시킵니다.

• 왜 start뒤에 end값을 보지 않아도 되나 궁금하다면, 누적합의 뒷부분의 배열의 크기가 무조건 더 크기 때문에 일반적인 투포인터 사용 조건과 일치합니다.

• 즉 인덱스 1번과 인덱스5번으로 이미 충분히 큰 값이 나왔기 때문에 인덱스 6번을 볼 때 다시 인덱스 1을 볼 필요가 없기 때문입니다.

주의 할 점

투포인터 알고리즘을 아에 모르고 누적합만 알고 있어서 처음에 상당히 헤맸습니다.

그래서 투포인터 관련된 강의를 보고 다시 문제를 푸니 쉽게 풀리네요,,

역시 알고리즘은 많은 유형의 문제를 풀어봐야 응용도 가능한 것 같습니다. 골드라 꽤 어렵군요

반성 및 고찰

처음에 뭔가 특별한게 떠오르지 않아서 일반 누적합에 다른 값을 빼가며 접근했었다. 그러나 돌아온건 시간초과였고 투 포인터로 접근해서 결국 해결하였다.

시간 초과 코드

#include <iostream>
using namespace std;
long long input[100001];
long long sum_input[100001];
int main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	int n,m;
	cin >> n >> m;
	int start_idx = -1;
	for (int i = 0; i < n; i++){
		cin >>input[i];
		if (i != 0)
			sum_input[i] = sum_input[i - 1] + input[i];
		else 
			sum_input[i] = input[i];
		if (sum_input[i] >= m && start_idx == -1)
			start_idx = i;
	}
	int ret = 1000000000;
	if (start_idx == -1){
		cout << 0 <<"\n";
		return (0);
	}
	int len = 100001;
	for (int i = start_idx; i < n; i++){
		int cnt = 0;
		if (sum_input[i] != m){
			for (int j = i - 1; cnt <  m && j >= 0; j--){
			cnt = sum_input[i] - sum_input[j];
			len = i - j;
			}
		}
		else 
			len = i + 1;
		if (len < ret)
			ret = len;
	}
	if (len == 100001)
		ret = 1;
	cout << ret << "\n";
}

Uploaded by N2T