BOJ 18251 : 제목 생략

18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (acmicpc.net)

18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

 

 

시간 복잡도:

• O(Nlog^2N)

 

알고리즘:

• 트리의 순회; 중위 순회
• DP

 

이 문제는 생각을 잘 하면 풀리는 것 같습니다. 먼저 하나의 문제를 예시로 들겠습니다.

 

정수 리스트 S가 주어졌을 때, 연속 최대 부분 합을 구하는 것입니다. 이게 무슨 소리냐면, 연속한 구간을 더했을 때 그 값이 최대가 되는 것을 말합니다.

 

S

8

-5

7

-2

-1

1

0

 

와 같은 리스트가 있을 때, 연속 최대 부분 합은 8, -5, 7을 더한 10입니다. 예상하셨다시피, 이 문제는 DP로, O(N) 안에 풀 수 있습니다. 자세한 설명은 생략하겠습니다. 밑의 코드를 참조하세요.

 

#include <iostream>
#include <algorithm>

using namespace std;

int N, arr[1001], dp[1001];

int main() {

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    dp[0] = 0; int ans = -2147480000;
    for (int i = 1; i <= N; i++) {
        if (dp[i - 1] < 0) dp[i] = arr[i];
        else dp[i] = dp[i - 1] + arr[i];
        ans = max(dp[i], ans);
    }

    cout << ans << endl;
}

 

 

이 문제는 이 기법을 조금 응용합니다. 이 문제는 트리의 높이가 추가되었네요. 똑같이 테이블을 트리의 높이를 포함해서,

 

≫ dp[i][j][k] = 높이 i ~ 높이 j 의 직사각형을 만들 때, k번째 노드를 포함하는 직사각형 중 가중치의 최댓값

 

사실 DP 배열은 필요하지 않습니다. 바로 전의 값만 알면 되기 때문이죠. 또한, 노드 간의 순서를 바꾸지 말아야 하니 중위 순회 방법을 응용할 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;
#define int long long
#define MAXN 262144
#define MAXH 19

int N, H, arr[MAXN];
vector<pair<int, int> > dt;

void inorder(int node, int depth) {

    if (depth < H) inorder(node * 2, depth + 1);
    dt.push_back({arr[node], depth});
    if (depth < H) inorder(node * 2 + 1, depth + 1);
}

signed main() {

    cin >> N; H = log2(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    inorder(1, 1);

    int ans = -876543212345678909;
    for (int i = 1; i <= H; i++) {
        for (int j = i; j <= H; j++) {
            int dp = 0;
            for (int k = 0; k < N; k++) {
                if (dt[k].second < i || dt[k].second > j) continue;
                if (dp < 0) dp = dt[k].first;
                else dp += dt[k].first;
                ans = max(dp, ans);
            }
        }
    }

    cout << ans << endl;
}