c언어 1806번 부분합 (백준)

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int n = 0;
	int s = 0;
	int i = 1;
	int ans = 100001;
	scanf("%d %d", &n, &s);  //동적할당 (heap메모리)
	long long int *a = (long long int*) malloc(sizeof(long long int) * (n+3));
	
	a[0] = 0;
	while(i <= n) { //부분합 만들기
		static int tmp = 0;
		scanf("%d", &tmp);
		if(tmp >= s) ans = 1; //하나만으로도 s이상이면 정답은 1
		a[i] += a[i-1] + tmp;
		i++;
	}
	
	if(ans == 1) { //정답이 1이면 바로 종료
		printf("%d", ans);
		return 0;
	}
	if(a[n] < s) { //모든걸 다합쳐도 s미만이면, 정답은 0
		printf("0");
		return 0;
	}
	
	int left = 0; //왼쪽 포인터
	int right = 2; //오른쪽 포인터
	
	while(1) {	
		if(a[right]-a[left] >= s) { //s이상이면 왼쪽을 증가시켜 범위를 좁히고,
			int tmp = right-left;
			if(tmp < ans) ans = tmp;
			if(ans == 2) break; //반복문에선 정답의 최솟값이 2이므로, 바로 탈출한다.
			left++;
		} else { //s미만이면 오른쪽을 증가시켜 범위를 늘린다.
			if(right==n) break; //오른쪽이 이미 끝가지 왔으면, 반복문을 종료 
			right++;
		} 
	}
	printf("%d", ans);
    return 0;
}

 

 

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

1806번: 부분합

 

 

풀이 

1. n과 s을 입력받는다.

2-1. 숫자들을 n개 입력받으나, 배열에 부분합으로 저장한다. 

2-2.  단 입력받은 수가 s보다 크면 정답은 1이다. 또한 모든 수를 다 합쳤으나, s보다 작으면 정답은 0이다.

3. 왼쪽포인터는 0에서, 오른쪽 포인터는 2에서 시작한다.

4. 요소들의 합보다 s가 작으면 왼쪽 포인터를 증가, 반대면 오른쪽 포인터를 증가한다. 단 오른쪽 포인터가 n에 다다르고 1을 더 증가시키려는 경우에 (불가하므로) while문을 나온다.

5. ans을 출력한다.