코드업 3007번

이 글에서는 코드업 3007번 문제를 풀이해보도록 하겠습니다.

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

기억력 테스트 7

---

문제 설명

 

주현이 엄마는 '기억력 테스트 6'이 너무 가혹해서인지 이번에는 좀 쉬운 테스트를 하기로 했다.

이번에도 n개의 숫자를 불러 주고, m개의 질문을 한다.

질문은 두 수 a, b를 이야기 하는데, a번째와 b번째 사이에 불렀던 수들의 합을 묻는다.

예를 들어, 3 5 2 1 4 3 의 숫자를 불러주고, 2, 4라고 질문하면 2번째에서 4번째 불렀던 숫자들의 합인 8을 대답해야 한다.

이번 테스트를 무사히 통과하면 '닌자 고'의 4종 캐릭터 장난감을 받을 수 있다.

---

입력

 

첫째 줄에 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개의 입력된 정수에서 a번째부터 b번째까지 수들의 합을 출력하면 됩니다. 사실 보자마자 아래 코드를 곧바로 짰으나...

#include <stdio.h>

int a[1000];
int n, m;

int f(int c, int b)
{
	int sum = 0;
	for(int i = 0; i < b-c+1; i++)
	{
		sum += a[c+i-1];
	}
	return sum;
}


int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	for(int i = 0; i < m; i++)
	{
		int c, b;
		scanf("%d %d", &c, &b);
		printf("%d\n", f(c, b));
	}
}

 시간이 너무 오래걸립니다.

문제를 다시 보니, n, m의 범위가 엄청나게 큽니다. 일반적인 방법으로는 할 수 없겠군요..

그래서, $1$번부터 $k$번째까지 합을 모두 계산해놓고, 이를 $S_k$라 하면 $a$번째부터 $b$번째까지 수들의 합은 $S_b-S_{a-1}$ 라는 것을 이용하고자 하였습니다. 먼저 순서도를 짜봅시다.

이를 바탕으로 코드를 짜보았습니다.

#include <stdio.h>

int a[1000000];
int n, m;
int a1, a2;
int mem[1000000];

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	long long int sum = 0;
	for(int i = 0; i < n; i++)
	{
		sum = sum + a[i];
		mem[i] = sum;
	}
	for(int i = 0; i < m; i++)
	{
		int a1, a2;
		scanf("%d %d", &a1, &a2);
		printf("%d\n", mem[a2-1] - mem[a1-2]);
	}
}

이렇게 하니 시간 초과 없이 풀 수 있었습니다. 일일이 합을 매번 계산하는 것이 너무 오래걸리다보니, 미리 계산해놓은 값들을 이용하여 계산하는 것이 효율적인 코드를 짜는 방법이었습니다.

코드 설명은 위의 설명과 큰 차이가 없으니 생략하도록 하겠습니다.

---

이렇게 코드업 3007번 문제를 풀이해보았습니다.