트리의 깊이 우선 탐색 순서 최적화

주어진 트리에서 각 노드는 고유한 가중치를 가지고 있으며, 루트 노드는 1번입니다. DFS 순서에서 짝수 위치에 있는 노드들의 가중치 합을 최대화하는 것이 목표입니다.

문제 해결 방법

이 문제는 트리형태의 동적 프로그래밍(DP)으로 접근할 수 있습니다. 각 서브트리가 제공할 수 있는 최대 점수를 계산하며 진행합니다. 서브트리를 구성하는 노드 수가 홀수인지 짝수인지를 기준으로 상태를 나누며, 자식 노드들의 상태에 따라 최적 값을 선택합니다.

코드 예시

#include 
using namespace std;

struct TreeNode {
    long long weight;
    vector<int> children;
};

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int nodeCount;
        cin >> nodeCount;
        vector<TreeNode> nodes(nodeCount + 1);
        for (int i = 1; i <= nodeCount; ++i) {
            cin >> nodes[i].weight;
        }
        for (int i = 0; i < nodeCount - 1; ++i) {
            int u, v;
            cin >> u >> v;
            nodes[u].children.push_back(v);
            nodes[v].children.push_back(u);
        }

        // DP 배열 초기화
        vector dp(nodeCount + 1, vector<long long>(2, 0));
        function dfs = [&](int x, int parent) {
            if (nodes[x].children.size() == 1 && x != 1) {
                dp[x][0] = nodes[x].weight;
                return;
            }

            bool hasOddChild = false;
            vector<long long> gains;
            for (auto &child : nodes[x].children) {
                if (child == parent) continue;
                dfs(child, x);
                if ((nodes[child].children.size() % 2) == 1) hasOddChild = true;
                gains.push_back(dp[child][0] - dp[child][1]);
                dp[x][0] += dp[child][1];
            }

            if (hasOddChild) {
                sort(gains.begin(), gains.end(), greater<long long>());
                for (size_t i = 0; i < gains.size() / 2; ++i) {
                    dp[x][0] += gains[i];
                }
            }
            dp[x][1] = dp[x][0];
            if (gains.size() % 2 == 1) dp[x][1] += gains[gains.size() / 2];
            dp[x][0] += nodes[x].weight;
        };

        dfs(1, -1);
        cout << dp[1][1] << "\n";
    }
}

비트 연산 최적화 문제

주어진 이진 문자열에서 가능한 모든 조합을 통해 마지막 남은 값이 '1'이 되도록 하는 경우의 수를 계산합니다.

문제 해결 방법

연속된 두 비트를 하나로 줄이는 연산을 통해 가능한 모든 경우를 시뮬레이션합니다. 각 위치별로 '1'이 마지막까지 남을 확률을 계산하여 이를 바탕으로 총 경우의 수를 도출합니다.

코드 예시

#include 
using namespace std;

const int MOD = 998244353;

long long modpow(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    int length;
    cin >> length;
    vector<int> bits(length + 1);
    for (int i = 1; i <= length; ++i) cin >> bits[i];

    vector<long long> ways(length + 1, 0);
    ways[0] = 1;
    for (int i = 1; i <= length; ++i) {
        ways[i] = ways[i - 1] * (2 * i - 1) % MOD;
    }

    vector<long long> invWays(length + 1, 0);
    for (int i = 1; i <= length; ++i) {
        invWays[i] = modpow(i, MOD - 2);
    }

    long long totalWays = 0;
    for (int i = 1; i <= length; ++i) {
        if (bits[i]) {
            long long leftWays = ways[i - 1];
            long long rightWays = ways[length - i];
            long long comb = (leftWays * rightWays) % MOD;
            comb = (comb * invWays[i - 1]) % MOD;
            totalWays = (totalWays + comb) % MOD;
        }
    }
    cout << totalWays << "\n";
}