c언어 11659번 구간 합 구하기 4 (백준)

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

11659번: 구간 합 구하기 4

 

 

 

 

 

#include <stdio.h>
#include <stdlib.h> //malloc 함수 이용!

int main(void)
{
	int n, m;
	scanf("%d%d", &n, &m); //몇 개?, 몇 번?
	//동적 메모리 할당
	int *arr = (int*) malloc(sizeof(int) * (n+1));
	int *nu = (int*) malloc(sizeof(int) * (n+1));
	
	nu[0] = 0; //0번째 때의 수의 합은 0 이다.
	for(int i =1; i<=n; i++) //1부터 n까지의 합을 구함
	{
		scanf("%d", &arr[i]);
		nu[i] = nu[i-1] + arr[i]; //1까지의 합, 2까지의 합... n까지의 합
	}
		
	while(m>0)
	{
		static int i, j;
		scanf("%d%d", &i, &j);
		printf("%d\n", nu[j]-nu[i-1]); //ex 1 3 이면 첫번째 부터 3번째까지 수의 부분합을 의미하므로
		m--;                           //3번째까지의 합에 0번째의 합을 빼면 구할 수 있다.
	}
	free(arr); //동적 메모리 끝
    free(nu); //동적 메모리 끝
	return 0;
}

 

 

• 풀이

1) N, M을 입력받고, N만큼 (또는 넉넉하게 N+1만큼) 동적으로 메모리를 2개 할당한다. 하나는 (int *arr) 수를 입력받기위해, 나머지 하나는(int *nu) 1부터 i까지의 합을 저장하기위해.

 

<코드>

int n, m;
scanf("%d%d", &n, &m); //몇 개?, 몇 번?
//동적 메모리 할당
int *arr = (int*) malloc(sizeof(int) * (n+1));
int *nu = (int*) malloc(sizeof(int) * (n+1));

 

2) 1부터 i (i = 1 ~ N) 까지의 수열의 합을 구한다. 그리고 이를 저장한다.

 

<코드>

nu[0] = 0; //0번째 때의 수의 합은 0 이다.
for(int i =1; i<=n; i++) //1부터 n까지의 합을 구함
{
scanf("%d", &arr[i]);
nu[i] = nu[i-1] + arr[i]; //1까지의 합, 2까지의 합... n까지의 합
}

 

3) x번째 수부터 y번째 수까지의 부분합을 구한다.

부분합 = y번째 까지의 수열의 합 - (x-1)번째 까지의 수열의 합

이를 m번 반복하면 된다!

 

<코드>

while(m>0)
{
static int i, j;
scanf("%d%d", &i, &j);
printf("%d\n", nu[j]-nu[i-1]); //ex 1 3 이면 첫번째 부터 3번째까지 수의 부분합을 의미하므로
m--;                           //3번째까지의 합에 0번째의 합을 빼면 구할 수 있다.
}

 

4) 마무리한다. 동적으로 할당받은 메모리들은 다 풀어주고, 종료한다.

 

<코드>

free(arr); //동적 메모리 끝
    free(nu); //동적 메모리 끝
return 0;