[구름IDE] 특정 구간의 합(★3)

문제

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include<iostream>
#include<vector>
 
int main() {
    std::vector<int> sum;
    std::vector<int> numbers;
    int N{}, left{}, right{};
 
    std::cin >> N;
    sum.assign(N, 0);
 
    for (int i = 0; i < N; ++i) {
        int value{};
        std::cin >> value;
        numbers.emplace_back(value);
 
        if (i == 0)
            sum[i] = value;
        else
            sum[i] = sum[i - 1] + value;
    }
 
    std::cin >> left >> right;
    left -= 2;
    right -= 1;
 
    if (left < 0)
        std::cout << sum[right] << "\n";
    else
    std::cout << sum[right] - sum[left] << "\n";
}
 

후기

이 문제를 해결하기 위한 키워드는 동적 계획법(DP)이다.

동적 계획법은 메모이제이션 기법을 사용해서 문제를 빠르게 풀어내는 알고리즘 기법이다. 자세한 동적 계획법의 설명은

아래 관련 글에 올려놨다.

오랜만에 동적 프로그래밍(DP)을 이용해서 문제를 풀어보았다. 해당 문제에서는 테스트 케이스가 적어서 사실상 예시만 풀어도 합격하는 수준이다. 그래서 0을 입력했을 때에는 문제가 생기지만 통과한다. 소스코드에서는 문제가 생기지 않도록 작성하였다. 앞으로도 동적 프로그래밍과 탐색 알고리즘 위주로 문제를 풀어갈 생각이다.