[백준 11441] 합 구하기

[백준 11441] 합 구하기

문제 출처 : https://www.acmicpc.net/problem/11441

---

문제

---

N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

출력

---

총 M개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다.

예제 입력

5
10 20 30 40 50
5
1 3
2 4
3 5
1 5
4 4

예제 출력

60
90
120
150
40

• 문제 이해하기

 첫 줄에 준 숫자(n)만큼, 다음 줄에 n개의 수를 작성한다. 세번째 줄에 준 숫자(m)만큼, 다음 줄 부터 m개의 원하는 구간의 숫자 합을 구해 출력하는 문제다. 이때 구간은 내가 설정한 숫자만큼의 크기에서 작성해야 하고, n과 m은 1이상 10만 이하이고 두번째 줄에 작성하는 숫자의 크기는 -1000부터 1000 사이의 숫자로 작성해야 한다.  

• 계획 및 문제 해결

구간의 합을 구하는 가장 좋은 방법은 무엇일까? 위의 예제를 활용해보자.

10 20 30 40 50이 입력되었다면, 아래와 같은 규칙을 가질 것 이다.

2~4구간 합은? (20+30+40) -> 1~4구간 합 - 1구간 합 -> (10+20+30+40) - 10

3~5구간 합은? (30+40+50) -> 1~5구간 합 - 2구간 합 -> (10+20+30+40+50) - (10+20)

이처럼 두 구간을 정했을 때, 뒤에 입력된 구간까지 저장된 총 합에서 앞에 입력된 구간의 바로 앞까지 저장된 합을 빼면 되는 규칙을 발견했다.

그렇다면, 해당구간까지의 합을 저장할 배열도 필요할 것이다.

이제 이러한 규칙을 코드로 작성해보자.

두 번째 줄에 입력되는 수를 배열에 저장하면서, 각 구간 별로 총 합을 더해놓는 sum 배열을 만들었다. 배열을 만들 때 STL 벡터를 사용해보았다. 합계를 저장할 sum배열의 크기를 상수화 시키지 않기 위해서다.

1

2

3

vector<int> v(100001); // 100000개를 저장하는 벡터 생성

vector<int> sum(line + 1); // 합계 저장할 벡터 생성

vector<int> result(100001); // 결과 출력 벡터 생성

cs

개수를 최대 10만까지 넣을 수 있기 때문에, 배열의 크기를 각각 100001로 잡았다.

합계를 저장할 벡터 sum은 1부터 시작할 수 있도록 배열 크기에 +1을 추가시켰다.

우선 첫 줄에 입력할 수를 line이라는 이름의 변수로 선언하고, line만큼 for문을 돌려서 v배열에 값을 넣었다.

그리고 sum배열에는 재귀 함수를 통해 해당 위치까지의 모든 합을 저장시키도록 만들었다.

for (int i = 1; i <= line; i++) {
    cin >> v[i];
    sum[i] = v[i] + sum[i - 1];
}

이제 sum배열에는 1부터 해당 배열까지의 합이 저장되어있는 상태다.

앞으로 입력될 구간에서 이 sum배열을 활용하면 된다.

세번째 줄에 입력할 수는 line2라는 이름의 변수를 선언했고, 구간의 시작을 start, 끝을 end로 지정해 결과 값을 result 배열에 저장했다.

int line2;
cin >> line2;
 
for (int j = 1; j <= line2; j++) {
    int start, end;
    cin >> start >> end;
    result[j] = sum[end] - sum[start - 1];
}

이제 result배열만 출력시켜주면 내가 입력한 수만큼의 구간 마다 합계를 나타내 줄 것이다.

for (int z = 1; z <= line2; z++) {
    cout << result[z] << endl;
}

• 전체 소스 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int line;
    cin >> line;
 
    vector<int> v(100001); // 100000개를 저장하는 벡터 생성
    vector<int> sum(line + 1); // 합계 저장할 벡터 생성
    vector<int> result(100001); // 결과 출력 벡터 생성
                              
 
    for (int i = 1; i <= line; i++) {
        cin >> v[i];
        sum[i] = v[i] + sum[i - 1];
    }
 
    int line2;
    cin >> line2;
 
    for (int j = 1; j <= line2; j++) {
        int start, end;
        cin >> start >> end;
        result[j] = sum[end] - sum[start - 1];
    }
 
    for (int z = 1; z <= line2; z++) {
        cout << result[z] << endl;
    }
 
 
    return 0;
}