[C/C++] 코드업(codeup) 3007번 기억력 테스트 7

▽문제 바로가기

https://codeup.kr/problem.php?id=3007

기억력 테스트 7

---

입력

첫째 줄에 n과 m이 입력된다. ( 1 <= n <= 1,000,000 ) , ( 1 <= m <= 100,000 )

둘째 줄에 n개의 정수가 공백으로 분리되어 입력된다. (입력수의 범위 : -1,000 ~ 1,000)

셋째 줄부터 m개의 질문이 입력되는데, 시작수 a와 마지막 수 b가 입력된다. ( 1 <= a <= b <= n ) 

 

출력

질문의 순서대로 각 줄에 a번째와 b번째 사이에 불렀던 수들의 합을 출력한다.

 

문제 풀이

 

구간 합을 출력하는 문제입니다. n은 숫자의 개수로 최대 백만 개가 주어졌고, m은 구하고자 하는 구간의 개수로 최대 십만 개 까지 주어집니다.

 

즉 최대 백만개의 루프를 십만 번 반복할 수 있습니다.(1,000,000 * 100,000 = 100,000,000,000)

딱 봐도 시간 초과가 날 것 같아서 메모이제이션으로 풀었습니다.

 

해결방법은 [0]부터 [0]까지, [0]부터 [1]까지, [0]부터 [2]까지...

전부 구해서 memo배열에 저장합니다.

 

2 ~ 4 구간의 합은 [3]까지의 합 - [0]까지의 합입니다.

즉, a ~ b 구간의 합은 memo[b-1] - memo[a-2] 입니다.

 

#include <stdio.h>

int main(){
	
	int n, m;
	scanf("%d%d", &n, &m);
	int arr[n];
	for(int i=0;i<n;i++) scanf("%d", &arr[i]);
	
	int ab[n][2];
	for(int i=0;i<m;i++) scanf("%d%d", &ab[i][0], &ab[i][1]);
	
	//구간 저장하기 [0] ~ [0], [0] ~ [1], [0] ~ [2] ... 
	int memo[n+1];
	int result = 0;
	for(int i=0;i<n;i++){
		result+=arr[i];
		memo[i] = result;
	}
	
	//출력 a ~ b 의 합은 memo[b-1] - memo[a-2] 
	for(int i=0;i<m;i++) printf("%d\n", memo[ab[i][1]-1]-memo[ab[i][0]-2]);
	
	return 0;
}