C++로 증가 수열에서 만들 수 있는 최대 합계(tally) 구하기

문제 설명

두 개의 정수 n과 m이 주어지고, 네 개의 정수 {ai, bi, ci, di}로 이루어진 k개의 튜플이 있다고 가정해 봅시다. 배열 a, b, c, d가 주어지며, a[i]는 i번째 튜플의 a 값에 해당합니다.

이제 n개의 양의 정수로 구성된 수열 dp를 생각해 보겠습니다. 이 수열은 다음 조건을 만족해야 합니다.

1 <= dp[1] < dp[2] < ... < dp[n] <= m

여기서 'tally'라는 지표를 정의합니다. tally는 dp[b[i]] − dp[a[i]] = c[i]를 만족하는 모든 인덱스 i에 대한 d[i]의 합입니다. 만약 해당 조건을 만족하는 i가 하나도 없다면 tally는 0이 됩니다. 우리가 구해야 할 것은 dp가 가질 수 있는 최대 tally 값입니다.

예를 들어 입력이 다음과 같다고 해봅시다.

• n = 4, m = 5, k = 4
• a = {2, 2, 3, 5}
• b = {4, 3, 4, 6}
• c = {4, 3, 3, 4}
• d = {110, 20, 20, 40}

이 경우 출력은 130이 됩니다.

풀이 접근 방식

이 문제는 가능한 모든 증가 수열 dp를 생성한 뒤, 각 경우에 대해 tally를 계산하고 그중 최댓값을 찾는 완전 탐색(브루트 포스) 방식으로 해결할 수 있습니다. 절차는 다음과 같습니다.

1. 크기가 각각 100, 100, 100, 100, 10인 배열 A, B, C, D, dp를 선언합니다.
2. 재귀 함수 depthSearch(c, l)를 정의합니다.
   • c가 n과 같으면(수열을 모두 채운 경우) total을 0으로 초기화하고, i를 0부터 k−1까지 순회하면서 dp[B[i]] − dp[A[i]] == C[i]를 만족하면 total에 D[i]를 더합니다. 이후 res를 total과 비교해 더 큰 값으로 갱신한 뒤 반환합니다.
   • 그렇지 않으면 j를 l부터 m까지 반복하면서 dp[c] = j로 설정하고 depthSearch(c + 1, j)를 재귀 호출합니다. 시작값을 l로 제한함으로써 수열이 항상 엄격하게 증가하도록 보장합니다.
3. solve 함수에서 입력 배열 a, b, c, d를 전역 배열 A, B, C, D에 복사하고, 0 기반 인덱스를 맞추기 위해 A[i]와 B[i]를 1씩 감소시킵니다.
4. depthSearch(0, 1)을 호출한 뒤 res를 반환합니다.

예제 코드 (C++)

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

int n, m, k, res = 0;
int A[100], B[100], C[100], D[100], dp[10]; 

void depthSearch(int c, int l){
   if(c == n){
      int total = 0;
      for(int i = 0; i < k; i++) {
         if(dp[B[i]] - dp[A[i]] == C[i]) total += D[i];
      }
      res = max(res, total);
      return;
   }
   for(int j = l; j <= m; j++){
      dp[c] = j;
      depthSearch(c + 1, j);
   }
}
int solve(int a[], int b[], int c[], int d[]){
   for(int i = 0; i < k; i++){
       A[i] = a[i], B[i] = b[i], C[i] = c[i], D[i] = d[i]; A[i]--, B[i]--;
   }
   depthSearch(0, 1);
   return res;
}
int main() {
   n = 4, m = 5, k = 4;
   int a[] = {2, 2, 3, 5}, b[] = {4, 3, 4, 6}, c[] = {4, 3, 3, 4}, d[] = {110, 20, 20, 40};
   cout<< solve(a, b, c, d);
   return 0;
}

입력

n = 4, m = 5, k = 4
a = {2, 2, 3, 5}
b = {4, 3, 4, 6}
c = {4, 3, 3, 4}
d = {110, 20, 20, 40}

출력

130

복잡도 분석

이 알고리즘은 길이 n의 모든 증가 수열 조합을 탐색하므로 시간 복잡도는 대략 O(C(m, n) × k)입니다. 따라서 n과 m이 작은 경우에 효율적이며, 입력 크기가 커지면 동적 계획법(DP) 등의 최적화 기법을 적용하는 것이 좋습니다.