BOJ_1806_부분합

문제 이름 : 부분합

문제 유형 : 두 포인터

작성 언어 : C,C++

 

 

문제

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

 

풀이

예제 입력에서 합이 15이 되는 수열 -> (5, 10) 길이 : 2

 

이 문제는 반복문에서 수열을 따라가며 합이S 이상이 될때까지 더해주며 count를 계산해주는부분 (right)과

합이 S 이상일때 count를 빼주며 최소길이를 저장해가는 (left) 로 구성하여 풀면 된다.

 

 

 

작성 코드

#include <iostream>
#include <stdio.h>

using namespace std;
 
int a[100000]={0};

int main()
{
	int N,S,sum=0;
	int count=0;
	int min_count=100001;
	scanf("%d %d",&N,&S);
	
	int left=0;
	int right=left;
	
	for(int i=0;i<N;i++)
	{
		scanf("%d",&a[i]);
	} //입력부분 
	
	
	for(int i=0;i<2*N;i++)
	{
		if(sum<S)
		{
			if(right>N) break;
			sum+=a[right];
			right++;
			count++;
		}
		else
		{
			if(min_count>count) min_count=count;
			sum -= a[left];
			left++;
			count--;
		}
			
	}
	
	if(min_count!=100001)
		printf("%d",min_count);
	else
		printf("0");
}

 

 

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

1806번: 부분합