[BaekJoon 11659번] 구간 합 구하기 4(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

11659번: 구간 합 구하기 4

 

 

[문제 설명]

 

 

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

 

[입력]

 

 

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

 

[출력]

 

 

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

 

[제한]

 

 

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

 

 

[입출력 예]

 

 

입력	출력
5 3 5 4 3 2 1 1 3 2 4 5 5	12 9 1

 

 

[문제 풀이]

 

 

문제를 보았을 때 직관적으로 떠올릴 수 있는 풀이는 2중 for문을 이용하는 방법이다.

처음에 이 문제를 접했을 때 2중 for문을 사용하여 제출하였지만, 시간 초과가 발생했다.

 

 

그래서 생각한 문제 풀이 방법은 누적된 합을 배열에 저장하는 방법이다.

우선 입출력 예를 이용하여 설명해보도록 하겠다.

 

1. 누적된 합을 저장할 배열을 선언한다. (배열은 입력 받을 수의 개수보다 +1이 큰 사이즈로 정해준다.)

 

2. 5개의 수인 5 4 3 2 1을 입력으로 받으면서, 누적된 합을 저장할 것이다.

 

먼저 5부터 입력을 받으면 1번 인덱스는 5로 값이 변경이 된다.

 

다음 4의 입력을 받는다.

2번 인덱스는 5 + 4 인 9로 값이 변경이 된다.

 

다음 3의 입력을 받는다.

3번 인덱스는 5 + 4 + 3 인 12로 값이 변경이 된다.

 

위와 같이

다음 2의 입력을 받을 때 4번 인덱스는 5 + 4 + 3 + 2 인 14로 값이 변경이 된다.

다음 1의 입력을 받을 때 5번 인덱스는 5 + 4 + 3 + 2 + 1 인 15로 값이 변경이 된다.

 

 

누적된 합을 구했으므로 구간의 합을 구할 수 있다!

아래와 같은 공식이 성립한다.

3. i번째 수부터 j번째 수의 합은 누적된 합이 저장된 배열[j] - 누적된 합이 저장된 배열[i - 1] 이다.

 

위의 공식을 적용하면,

입출력 예의 1번째 수부터 3번째 수 까지의 합은 12 - 0 = 12 이다.

입출력 예의 2번째 수부터 4번째 수 까지의 합은 14 - 5 = 9 이다.

입출력 예의 5번째 수부터 5번째 수 까지의 합은 15 - 14 = 1 이다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;
vector<int> number;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M; // 수의 개수, 합을 구해야하는 횟수
    number.resize(N+1);
    int sum = 0;
    for(int i = 1; i <= N; ++i) {
        int n; cin >> n;
        sum += n;
        number[i] = sum;
    }
    for(int k = 0; k < M; ++k) {
        int st, en; cin >> st >> en;
        cout << number[en] - number[st - 1] << '\n';
    }
    return 0;
}