TIL: 동적 프로그래밍과 세그먼트 트리를 활용한 최대 조개 개수 계산 최적화

문제 설명

정올시는 N × N 크기의 정방형 격자로 이루어진 도시이며, 각 지역에서는 최대 몇 개의 조개를 주울 수 있는지가 정해져 있다.
각 거주민은 오른쪽 혹은 위쪽으로만 이동하여 수산시장(0,0)으로 이동하며,
이동 중 지나가는 각 지역에서 최대한 많은 조개를 주운다.

이 문제에서 해결해야 할 것은 다음과 같다:
1. 초기 조개 개수를 기준으로 각 지역에서 최대로 팔 수 있는 조개 개수를 계산한 후, 그 합을 출력한다.
2. 이후 주어지는 변경 명령어 (U r c, D r c)에 따라 격자 내 특정 좌표의 최대 조개 개수를 변화시키고, 그에 맞춰 최대 조개 합을 업데이트하여 출력한다.

해결 방법

1. DP (Dynamic Programming) 기반 초기값 계산

• DP 테이블 dp[i][j] 를 만들어, 각 위치에서 수산시장까지 가는 최대 조개 개수를 누적 계산한다.
• 계산 방식:
  [
  dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + 초기값
  ]
• 이를 통해 O(N²)으로 초기 최대 조개 개수 합을 구할 수 있다.

2. 세그먼트 트리를 활용한 동적 업데이트

• U r c: (r, c) 위치의 조개 개수를 1 증가.
• D r c: (r, c) 위치의 조개 개수를 1 감소.
• 한 번 업데이트되면, 영향을 받는 모든 하위 지역의 dp[i][j] 값이 바뀌어야 하므로 세그먼트 트리를 활용하여 구간 업데이트를 수행한다.
• 영향을 받는 범위를 빠르게 찾아서, 세그먼트 트리 구간 업데이트를 활용하여 O(N log N) 에 처리한다.

코드 구현

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX_N 1510

// 세그먼트 트리 구조체
struct SegmentTree {
    int base = 1 << 11;
    int tree[1 << 12] = {0};

    void update(int l, int r, int v) {
        l += base; r += base;
        while (l <= r) {
            if (l & 1) tree[l] += v;
            if (~r & 1) tree[r] += v;
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }
    }

    int query(int p) {
        int res = 0;
        for (p += base; p; p >>= 1) res += tree[p];
        return res;
    }
} segment[MAX_N];

int N, dp[MAX_N][MAX_N], leftBound[MAX_N], rightBound[MAX_N];

// 특정 위치에서 값을 얻는 함수
int getValue(int row, int col) {
    return dp[row][col] + segment[row].query(col);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    
    ll totalMaxShells = 0;
    
    // 초기 조개 개수 입력 및 DP 계산
    for (int i = 1; i <= N; i++) 
        for (int j = 1; j <= N; j++) 
            cin >> dp[i][j];

    for (int i = 1; i <= N; i++) 
        for (int j = 1; j <= N; j++) {
            dp[i][j] += max(dp[i-1][j], dp[i][j-1]);
            totalMaxShells += dp[i][j];
        }
    
    cout << totalMaxShells << endl;
    
    // 변화 명령어 처리
    for (int iter = 0; iter < N; iter++) {
        char operation; int row, col;
        cin >> operation >> row >> col;
        int valueChange = (operation == 'U' ? 1 : -1);
        
        leftBound[row] = rightBound[row] = col;
        for (int i = row + 1; i <= N; i++) leftBound[i] = N + 1, rightBound[i] = 0;

        // 오른쪽 방향 최대 조개 값 갱신
        for (int curRow = row, curCol = col;;) {
            if (curCol < N && max(getValue(curRow, curCol), getValue(curRow - 1, curCol + 1)) + valueChange == max(getValue(curRow, curCol) + valueChange, getValue(curRow - 1, curCol + 1))) 
                curCol++;
            else 
                curRow++;
            
            if (curRow > N) break;
            rightBound[curRow] = curCol;
        }
        
        // 왼쪽 방향 최대 조개 값 갱신
        for (int curRow = row, curCol = col;;) {
            if (curRow < N && max(getValue(curRow, curCol), getValue(curRow + 1, curCol - 1)) + valueChange == max(getValue(curRow, curCol) + valueChange, getValue(curRow + 1, curCol - 1))) 
                curRow++;
            else 
                curCol++;
            
            if (curCol > N || curCol > rightBound[curRow]) break;
            leftBound[curRow] = min(leftBound[curRow], curCol);
        }
        
        // 세그먼트 트리 업데이트 및 총 최대 조개 수 조정
        for (int i = row; i <= N; i++) {
            if (leftBound[i] <= rightBound[i]) {
                segment[i].update(leftBound[i], rightBound[i], valueChange);
                totalMaxShells += valueChange * (rightBound[i] - leftBound[i] + 1);
            }
        }

        cout << totalMaxShells << endl;
    }
    
    return 0;
}

코드 설명

1. DP를 이용한 초기 최대 조개 개수 계산

• ( dp[i][j] ) 값은 ( \max(dp[i-1][j], dp[i][j-1]) + \text{초기값} ) 으로 설정한다.
• 모든 ( dp[i][j] ) 값을 합하여 초기 최대 조개 개수의 합을 구한다. ((O(N^2)))

2. 변경 명령어 적용

• ( (r, c) ) 위치의 값이 변할 경우, 영향을 받는 모든 아래 행을 찾아 업데이트해야 한다.
• 오른쪽으로 확장 ( (\text{rightBound}[i]) ), 왼쪽으로 확장 ( (\text{leftBound}[i]) ) 하여 변경 범위를 찾는다.
• 세그먼트 트리를 사용하여 ( O(\log N) ) 에 구간 업데이트를 수행.

3. 세그먼트 트리를 사용한 최적화

• 각 행별로 세그먼트 트리를 유지하여, ( dp[i][j] ) 값을 빠르게 조정.
• update(l, r, v): 특정 구간에 대해 값 증가/감소.
• query(p): 특정 열 ( p )의 변경된 값을 조회.
• 이를 통해 ( O(\log N) ) 으로 변경 적용 가능.

So...

이 문제에서는 동적 프로그래밍(DP)과 세그먼트 트리를 결합하여 격자 형태의 최적화 문제를 해결하는 방법을 익힐 수 있었다.

• 초기 DP 계산을 통해 ( O(N^2) ) 으로 초기 최대 조개 개수 합을 구함.
• 세그먼트 트리를 활용하여 ( O(N \log N) ) 으로 변경 적용.
• 좌우 범위를 찾아가며 변화 영향을 최소화하여 최적화.

이 방법을 통해 큰 입력에도 효율적으로 동작하는 최적의 해결 방법을 적용할 수 있었다.