[Baekjoon - 17017] Triangle: The Data Structure

난이도: Diamond V

 

태그

• Sparse Table → Range Maximum Query in O(1)
• Divide and Conquer
• Precomputation

 

풀이

1. 한 변의 길이가 \( K \)인 정사각형의 Range Maximum Query는 어떻게 처리할까?

사실 어느 정도 웰노운이긴 합니다.

 

\( 2^k \le K \)인 최대 \( k \)를 찾은 뒤, 아래와 같이 쿼리를 날리면 됩니다.

size 4의 정사각형으로 size 7의 RMQ 날리기

 

2. 한 변의 길이가 \( K \)인 이등변삼각형의 Range Maximum Query를, [1]의 아이디어로 처리할 수 있을까?

네. 가능합니다.

 

\( 2^k \le K \)인 최대 \( k \)를 찾은 뒤, 아래와 같이 쿼리를 날리면 됩니다.

size 4의 이등변삼각형으로 size 7의 RMQ 날리기.

 

대신에, 이 경우는 정사각형의 RMQ까지 같이 고려해줘야겠죠.

 

Intermission 1. Sparse Table을 쓰면 답이 잘 나오지만, 메모리 제한에 괜찮을까?

[1]과 [2]의 아이디어를 토대로, 아래 2개의 Sparse Table를 저장하는 생각을 해볼 수 있습니다.

\( S_{k, y, x} \) = \( (y, x) \)를 좌측 상단 점으로 하는, 한 변의 길이가 \( 2^k \)의 정사각형에 대한 RMQ.

\( T_{k, y, x} \) = \( (y, x) \)를 좌측 상단 점으로 하는, 한 변의 길이가 \( 2^k \)의 이등변삼각형에 대한 RMQ.

 

하지만 이대로면 \( 2 \times 13 \times 3000 \times 3000 = 234\,000\,000 \)칸의 메모리를 쓰게 됩니다.

약 892 MB가 나오니, 이대로는 MLE가 뜨겠죠.

 

3. 정말 모든 \( 2^k \)에 대한 Sparse Table이 필요할까?

저희가 필요로 하는 삼각형은 크기가 고정되어있습니다.

그러니, 쿼리에 필요한 \( k \)를 미리 찾은 뒤, 그 \( k \)에 대한 Sparse Table만 저장하는 방법을 생각해볼 수 있습니다.

 

그리고 이렇게 하면 실제로 메모리 제한 내로 들어옵니다.

\( 2 \times 3000 \times 3000 = 18\,000\,000 \)칸 = 약 68 MB죠.

 

주의할 점은, \( T_{k-1, *, *} \)를 계산하기 위해서는 \( S_{k-1, *, *}, T_{k-1, *, *} \)이 둘 다 필요하기 때문에

\( T \)를 계산하기 위한 \( S \)와, 나중에 삼각형 쿼리를 계산하기 위한 \( S \)를 따로 들고 있어야 합니다.

하지만 이렇게 해도, 약 136 MB 정도가 나오니 AC를 받을 수 있습니다.

 

4. 코드

int arr[3020][3020];
int tri[3020][3020], squ[3020][3020], squ2[3020][3020], tmp[3020][3020];
 
void Main(){
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            cin >> arr[i][j];
            tri[i][j] = squ[i][j] = squ2[i][j] = arr[i][j];
        }
    }
    int bt = 0; while ((1 << bt+1) <= k){ bt += 1; } int tt = 1<<bt;
    int kk = k-tt;
    int bs = 0; while ((1 << bs+1) <= kk){ bs += 1; } int ts = 1<<bs;
    for (int b = 1; b <= bt; b++){
        int d = 1 << b-1;
        for (int y = 1; y <= n; y++){
            for (int x = 1; x <= y; x++){
                tmp[y][x] = tri[y][x];
                if (y+d <= n){ tmp[y][x] = max(tmp[y][x], squ2[y+d][x]); }
                if (y+d <= n && x+d <= n){ tmp[y][x] = max(tmp[y][x], tri[y+d][x+d]); }
            }
        }
        for (int y = 1; y <= n; y++){
            for (int x = 1; x <= y; x++){ tri[y][x] = tmp[y][x]; }
        }
        for (int y = 1; y <= n; y++){
            for (int x = 1; x <= y; x++){
                tmp[y][x] = squ2[y][x];
                if (y+d <= n){ tmp[y][x] = max(tmp[y][x], squ2[y+d][x]); }
                if (x+d <= n){ tmp[y][x] = max(tmp[y][x], squ2[y][x+d]); }
                if (y+d <= n && x+d <= n){ tmp[y][x] = max(tmp[y][x], squ2[y+d][x+d]); }
            }
        }
        for (int y = 1; y <= n; y++){
            for (int x = 1; x <= y; x++){
                squ2[y][x] = tmp[y][x];
                if (b <= bs){ squ[y][x] = tmp[y][x]; }
            }
        }
    }
    ll ans = 0;
    for (int y = 1; y <= n-k+1; y++){
        for (int x = 1; x <= y; x++){
            if (tt == k){ ans += tri[y][x]; }
            else{
                ll res = max({tri[y][x], tri[y+k-tt][x+k-tt],
                              squ[y+tt][x], squ[y+k-ts][x],
                              squ[y+tt][x-tt+k-ts], squ[y+k-ts][x-tt+k-ts]});
                //cout << "RES " << y << ' ' << x << " = " << res << endl;
                ans += res;
            }
        }
    }
    cout << ans;
}