길이가 n-1인 배열 D와 두 개의 값 a, b가 주어져 있다고 가정해 봅시다. 어떤 군대에는 1부터 n까지 번호가 매겨진 n개의 계급이 존재하며, 계급 i에서 계급 i+1로 진급하는 데는 D[i]년이 필요합니다. 아말(Amal)은 방금 계급 'a'에 도달했지만, 실제 목표는 계급 'b'입니다. 우리는 그가 목표 계급에 도달하기까지 필요한 총 년수를 계산해야 합니다.
예를 들어 입력이 D = [5, 6]; a = 1; b = 3과 같다면, 출력은 11이 됩니다.
이 문제는 다음 단계를 따라 해결할 수 있습니다 -
n := size of D s := 0 for initialize i := a - 1, when i < b - 1, update (increase i by 1), do: s := s + D[i] return s
알고리즘 동작 원리
핵심 아이디어는 매우 간단합니다. 배열 D의 각 요소는 계급 사이의 진급 구간에 필요한 기간을 의미하므로, 시작 계급 a에 해당하는 인덱스(a - 1)부터 목표 계급 b 직전 인덱스(b - 2)까지의 값을 모두 더하면 됩니다. 즉, 반복문을 사용해 해당 구간의 합계만 구하면 원하는 답을 얻을 수 있습니다.
예제
더 잘 이해하기 위해 다음 C++ 구현 예시를 살펴보겠습니다 -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> D, int a, int b){
int n = D.size() + 1;
int s = 0;
for (int i = a - 1; i < b - 1; i++){
s = s + D[i];
}
return s;
}
int main(){
vector<int> D = { 5, 6 };
int a = 1;
int b = 3;
cout << solve(D, a, b) << endl;
}위 코드에서 solve 함수는 배열 D와 시작 계급 a, 목표 계급 b를 입력받아 반복문으로 구간 합을 누적한 뒤 반환합니다. main 함수에서는 예제 데이터를 넣어 결과를 출력합니다.
입력
{ 5, 6 }, 1, 3출력
11
결과가 11이 되는 이유는 다음과 같습니다. 계급 1에서 2로 진급하는 데 5년(D[0]), 계급 2에서 3으로 진급하는 데 6년(D[1])이 필요하므로, 총 5 + 6 = 11년이 소요됩니다.