[백준 1292번] 쉽게 푸는 문제 - C++ 풀이

https://www.acmicpc.net/problem/1292
(백준 문제 링크)

1. 문제 설명

문제

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.

이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.

하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.

2. 풀이

주어진 문제는 주어진 수열의 구간 합을 구하는 문제입니다. 해당 문제는 단순하게(naive) 구현하여도 풀 수 있지만, 누적합(Prefix Sum)을 통한 풀이를 소개하겠습니다.

누적합이란 주어진 수열에서 특정 위치까지의 원소 값(value)의 합을 저장하는 과정입니다.

예를 들어 문제에서 주어진 수열은 $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, ...$ 이며, 이를 누적합으로 변경하면 아래 형태와 같습니다.
$$1, (1+2), (1+2+2), (1+2+2+3), (1+2+2+3+3), (1+2+2+3+3+3), (1+2+2+3+3+3+4), ...$$

누적합은 수열의 구간에 대한 합을 미리 구해두는 것이기 때문에, 특정 구간에 대한 합을 반복적으로 계산하게 된다면, 이미 했던 계산을 다시 할 필요가 없게 해줍니다. (이 문제에서는 해당되지 않는 내용입니다)

예를 들어 (3, 5)구간에 대한 합을 계산한 뒤에 (3, 8) 구간에 대한 합이 필요하게 된다면, 이전에 계산해둔 (3, 5)구간에 대한 합을 이용하여 (3, 8)구간을 계산하는 것이 유리합니다.

누적합 배열은 주어진 수열에서 특정위치까지의 원소 값이 저장되어있다고 정의하며, 현재 위치가 N이라고 한다면 누적합 배열의 N-1번째에 현재 위치에 해당하는 원소 값을 더하면 누적합 배열의 현재 위치 값을 계산할 수 있습니다.

예를 들어 누적합 배열을 $prefix$, 수열을 $sequence$라고 한다면,
$prefix[N]=prefix[N-1] + sequence[N]$입니다.

이번 문제에서는 N이 1000이하이므로 주어지는 구간이 1000이하라는 뜻입니다.
1부터 49까지의 수열의 길이를 구해보자면, 1이 한 번, 2가 두 번, ..., 49가 49번 발생하므로 수열의 길이는 $1+2+3+...+49$ 입니다.

이는 $49\times 50\div 2$이므로, 1225입니다. 문제 제한보다 더 긴 수열이므로 1부터 49까지의 수열에 대한 누적합 배열을 만들어 문제를 해결하였습니다.

for(int i=1; i<50; i++) {
    for(int j=0; j<i; j++) {
        prefix_sum.push_back(prefix_sum.back()+i);
    }
}

결론적으로 주어지는 (A, B) 구간에 대한 구간 합은 누적합 배열 $prefix$를 이용하여 계산 가능하며, $prefix[A]$에는 A번째 값이 포함되어 있으므로, 빼서는 안됩니다.
즉, $prefix[B] - prefix[A-1]$이 정답입니다. 

 

 

3. 정답 코드

#include<iostream>
#include<vector>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    vector<int> prefix_sum(1, 0);
    for(int i=1; i<50; i++) {
        for(int j=0; j<i; j++) {
            prefix_sum.push_back(prefix_sum.back()+i);
        }
    }
    cout << prefix_sum[B]-prefix_sum[A-1];
}