Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 배열 요소 삭제 문제: 동적 계획법으로 최대 점수 구하기

문제 개념

N개의 원소를 가진 배열 A와 두 정수 l, r이 주어집니다. 단, 각 원소는 1 ≤ ax ≤ 105 범위를 가지며 1 ≤ l ≤ r ≤ N 조건을 만족합니다. 배열에서 임의의 원소 ax를 선택해 삭제하면, 값이 ax+1, ax+2 … ax+r 또는 ax-1, ax-2 … ax-l에 해당하는 모든 원소도 함께 제거됩니다. 이 연산 하나는 ax만큼의 점수를 얻게 됩니다.

목표는 배열의 모든 원소를 삭제하는 과정에서 얻을 수 있는 총 점수를 최대화하는 것입니다.

예제 1

2 1 2 3 2 2 1
l = 1, r = 1

출력:

8

값 2를 선택해 삭제하면, 주어진 l과 r 범위에 따라 (2-1)=1과 (2+1)=3도 반드시 함께 삭제해야 합니다. 이 과정을 배열에 남은 2가 없어질 때까지 반복하면, 총 점수는 2×4 = 8이 됩니다.

예제 2

2 4 2 10 5
l = 1, r = 2

출력:

19

먼저 2를 선택해 삭제하면 l=1, r=2 조건 때문에 4도 함께 제거됩니다. 이어서 5를 삭제하고, 마지막으로 10을 삭제합니다.

따라서 총 점수는 2×2 + 5 + 10 = 19입니다.

접근 방법: 동적 계획법

가장 먼저 배열에 등장하는 모든 값의 빈도수를 계산합니다. 어떤 값 X를 선택하면 [X-l, X+r] 범위에 포함된 값들이 한꺼번에 삭제된다고 생각할 수 있습니다. 이때 l과 r 중 더 작은 값을 기준으로 삼으면, X를 선택했을 때 어느 지점까지의 원소가 삭제되는지 명확하게 판단할 수 있습니다.

각 값 num에 대해 다음 두 가지 경우를 비교합니다.

  • num을 선택하지 않고 건너뛰는 경우: 직전 상태의 최대 점수를 그대로 가져옵니다.
  • num을 선택하는 경우: num × (num의 빈도수)에, 삭제 범위 바로 아래 지점까지의 최대 점수를 더합니다.

이 두 값 중 큰 것을 DP 테이블에 저장하며 1부터 배열의 최댓값까지 순차적으로 채워 나가면, 배열 전체를 삭제할 때 얻을 수 있는 최대 점수를 효율적으로 구할 수 있습니다.

C++ 구현 코드

// C++ 프로그램: 배열의 모든 원소를 삭제한 후 얻을 수 있는 최대 점수 구하기
#include <bits/stdc++.h>
using namespace std;

// 최대 점수를 반환하는 함수
int maxCost(int a[], int m, int L, int R){
    int mx1 = 0, k1;
    // 배열의 최댓값을 구합니다.
    for (int p = 0; p < m; ++p)
        mx1 = max(mx1, a[p]);
    // 모든 원소의 개수를 0으로 초기화합니다.
    int count1[mx1 + 1];
    memset(count1, 0, sizeof(count1));
    // 배열의 모든 원소에 대한 빈도수를 계산합니다.
    for (int p = 0; p < m; p++)
        count1[a[p]]++;
    // 삭제된 원소들의 점수를 저장할 배열입니다.
    int res1[mx1 + 1];
    res1[0] = 0;
    // L과 R 중 더 작은 범위를 선택합니다.
    L = min(L, R);
    for (int num1 = 1; num1 <= mx1; num1++) {
        // num1을 선택했을 때 어디까지 삭제되는지 결정합니다.
        k1 = max(num1 - L - 1, 0);
        // num1을 선택하는 경우와 선택하지 않는 경우 중 최댓값을 구합니다.
        res1[num1] = max(res1[num1 - 1], num1 * count1[num1] +
        res1[k1]);
    }
    return res1[mx1];
}

// 드라이버 프로그램
int main(){
    int a1[] = { 1, 1, 3, 3, 3, 2, 4 }, l1 = 1, r1 = 1;
    int a2[] = { 2, 4, 2, 10, 5 }, l2 = 1, r2 = 2;
    // 배열의 크기
    int n1 = sizeof(a1) / sizeof(a1[0]);
    int n2 = sizeof(a2) / sizeof(a2[0]);
    // 함수 호출로 최대 점수를 구합니다.
    cout<<"Maximum Cost for First Example:" << maxCost(a1, n1, l1,r1)<<endl;
    cout<<"Maximum Cost for Second Example:" << maxCost(a2, n2, l2,r2);
    return 0;
}

실행 결과

Maximum Cost for First Example:11
Maximum Cost for Second Example:19

코드 핵심 정리

  • count1 배열: 각 값이 배열에 몇 번 등장하는지 빈도수를 저장합니다.
  • res1 배열: 값 1부터 현재 값까지 고려했을 때 얻을 수 있는 최대 점수를 저장하는 DP 테이블입니다.
  • L = min(L, R): 삭제 범위를 보수적으로 계산해, 선택한 값과 인접한 값들을 확실하게 처리합니다.
  • 점화식: res1[num] = max(res1[num-1], num × count1[num] + res1[max(num-L-1, 0)])

시간 및 공간 복잡도

배열의 최댓값을 M이라고 하면, 빈도수 계산에는 O(N)의 시간이, DP 테이블을 채우는 데에는 O(M)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(N + M)이며, 빈도 배열과 DP 배열을 위한 공간 복잡도는 O(M)입니다.