[백준 BOJ] 11441번 합 구하기 (C++/cpp)

문제 설명

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

11441번: 합 구하기

 

접근 방법 - 누적 합 알고리즘을 활용한 기초 문제

백준의 11441번 문제는 누적 합 알고리즘을 활용하여 해결해야 하는 문제이다.

해당 문제는, 주어지는 수열에 대하여 특정 구간에 있는 숫자들의 총합들을 구하여 출력해야 하는 문제이다.

일일이 탐색하며 구하는 방법이 있긴 하지만, 테스트 케이스 및 수열의 길이가 크기 때문에 시간 초과가 날 가능성이 있다.

그렇기 때문에, 이 문제를 해결하기 전에는 누적 합에 대해 알아두는 것이 도움 될 것이다.

 

---

 

누적 합은, 단어 그대로 현재 구간까지 누적된 총합을 의미한다.

예를 들어 설명하기 위해, [1, 2, 3, 4, 5, 6, 7]이라는 수열 또는 배열이 있다고 가정하자.
필자는 그 수열 아래로 하나의 배열을 더 그려 넣었는데, 이것이 주어진 수열에 대해 각 누적 합을 저장한 배열이다.
15라는 숫자를 보자면, 이는 1+2+3+4+5의 결과라 볼 수 있는데 0번째 숫자~4번째 숫자를 합한 결과라고도 볼 수 있다.
누적 합 알고리즘은 이러한 원리를 통해서, 각 문제에 맞게 활용하면 된다.

 

---

 

필자는 위 알고리즘을 활용하여 문제를 해결하였다.

수열을 입력받으며 각 구간의 누적 합을 미리 저장해 두고, i~j 구간의 총합에 대해선 (j 구간까지의 누적합) - (i-1 구간까지의 누적합)으로 식을 구성하여 정답을 출력하게끔 하였다.

임의의 예시로 3~5 구간의 총합에 대해서는, (5구간까지의 누적합) - (2구간까지의 누적합)으로 구할 수 있다.

더 자세한 설명은 아래에 기재하니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 누적 합을 저장할 배열 sum을 전역 변수로 미리 선언해 둔다.

 

2) 숫자의 개수(n)를 입력받고, n의 크기만큼 각 숫자(num)를 입력받는다.

이때, num을 하나씩 입력받을 때마다 현재 구간(i)까지의 총합을 구하여 각 sum에 저장하도록 한다.

이전 구간까지의 총합(sum[i-1])에 현재 num값을 더하여, 이를 현재 구간까지의 총합(sum[i])으로 저장하면 된다.

 

3) 테스트 케이스의 수(t)를 입력받는다.

 

4) t의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 구간의 시작과 끝(start, end)을 입력받는다.

- 위의 설명대로, (0~end번째의 구간의 총합) - (0~start-1번째의 구간의 총합) 식으로 정답을 즉시 출력한다.

 

5) 모든 연산이 끝났다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 11441번 코드
int sum[100001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

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

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int start, end;
        cin >> start >> end;
        cout << sum[end] - sum[start - 1] << endl;
    }
}

 

제출 결과

(2023.04.08 백준 11441번 문제 제출 결과)