[c++] 백준 13325 - 이진 트리(비트마스크, dfs)

0. [c++] 백준  -

https://www.acmicpc.net/problem/13325

1. 풀이

 이번 문제를 풀기 위해서 생각을 해보았다. root에서 leaf까지 가중치를 더한 합이 모두 같아야 하고, 추가적으로 가중치들의 합이 최소가 되는 방법을 찾아 그 가중치의 합을 출력하는 문제이다.

 이때, 가중치의 합을 최소로 만드는 방법은 가장 상위 부분의 가중치를 우선적으로 더해주는 방법을 활용하면 최소로 만들 수 있었다.

 또한, 더해주는 가중치의 크기는 (구해야 하는 목표치) - (branch로 나뉘어진 부분에서 최대값)이 되고, 이 값들을 leaf부분에 각각 더해주고, 출력해야하는 가중치의 합에도 한번 더해준다.

이 코드의 핵심은 leaf만 유지하여 활용하는 메모리의 양을 줄일 수 있었다.

추가적으로, 위에 설명을 조금 간단하게 예시를 들어보겠다.

k=3이라는 입력이 처음으로 들어온 경우라면, leaf는 2^3인 8개가 나오게 되고, 입력에서는 2/4/8/개의 가중치가 들어올 것이다.

이때, 2개는 4/4개의 leaf에 더해주고, 4는 2/2/2/2개의 leaf에 더해주고 8개는 leaf에 각각 더해주면 된다.

이와 비슷한 방식으로 모든 leaf를 같게 만들어 주는데, 가장 큰 부분부터 시작하는 것이다.

4/4로 나누어서 MAX와 비교해서 가장 큰 것이 MAX와 같아지게 더해주는 방식으로 풀어나가는 것이다.

2. 소스코드

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<int> arr;
int ret;
int MAX;
 
void calc(const int& N, const int& depth) {
    bool check_this = false;
    for (int i = 0; i < (1 << depth); i++) {
        int temp_MAX = 0;
        for (int j = i * (1 << (N - depth)); j < (i + 1) * (1 << (N - depth)); j++) {
            temp_MAX = max(temp_MAX, arr[j]);
            if (temp_MAX == MAX)
                break;
        }
        if (temp_MAX == MAX)
            continue;
        ret += (MAX - temp_MAX);
        for (int j = i * (1 << (N - depth)); j < (i + 1) * (1 << (N - depth)); j++) {
            arr[j] += (MAX - temp_MAX);
        }
        if (MAX != temp_MAX && !check_this)
            check_this = true;
    }
    if (check_this && N > depth)
        calc(N, depth + 1);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, temp;
    cin >> N;
 
    arr.resize((1 << N));
    
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < (1 << i); j++) {
            cin >> temp;
            ret += temp;
            for (int k = j * (1 << (N - i)); k < (j + 1) * (1 << (N - i)); k++) {
                arr[k] += temp;
            }
        }
    }
 
    //for (int i = 0; i < (1<<N); i++) {
    //    cout << arr[i] << " ";
    //}
    for (int i = 0; i < (1<<N); i++) {
        MAX = max(MAX, arr[i]);
    }
 
 
    calc(N, 1);
 
    cout << ret;
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!