c언어 27968번 사사의 사차원 사탕 봉지 (백준)

#include <stdio.h>

int main(void) {
	int n, m;
	scanf("%d %d", &m, &n); //쿼리의 개수, 요소의 개수
	
	long long arr[n+1]; //long long
	arr[0] = 0; //없는 것은 0으로
	for(int i=1; i<=n; i++) { //요소들을 입력 받고
		scanf("%lld",&arr[i]);
		arr[i] += arr[i-1]; //누적 합 구하기
	}
	
	while(m--) { //m 개의 쿼리
		long long ans =0, find;
		scanf("%lld", &find); //find값이상이면서 가장 가까운 값을 찾아야 함
		
		int left = 1, right = n, mid;
		
		while(left <= right) { //이분탐색
			mid = (left+right)/2;
			if(arr[mid] >= find) { //find 이상이면
				ans = mid; //일단 정답으로 이때의 index을 저장
				right = mid-1; //오른쪽 범위를 줄임
			} else left = mid+1; //왼쪽 범위를 줄임
		}
		
		if(ans) printf("%lld\n", ans); //find 이상인 누적합이 있다면 그때의 인덱스를 출력
		else printf("Go away!\n"); //없다면
	}
}

 

풀이 : 누적합, 이분탐색

 

1. 쿼리의 개수와, 요소의 개수를 입력받습니다.

2. 요소들을 입력 받고 배열을 이용하여 누적합을 구합니다.

3. m개의 쿼리들을 이분탐색을 이용하여 찾을 값보다 같거나 크며 가장 작을 때의 인덱스를 탐색합니다.\

4. 있다면 그때의 인덱스를 출력하며 없다면 Go away! 을 출력합니다.

 

주의 long long으로 만들어야 합니다.

 

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

27968번: 사사의 사차원 사탕 봉지