문제

문제 링크

문제 접근

  • 이진트리의 리프 노드부터 거꾸로 올라오면서 각 노드에 도달하기 까지의 MAX 값을 저장한다.
  • 그 후에 위에서 부터 각 노드의 MAX 값에서 w(가중치)를 빼주면 이 값이 left와 right 노드로 가는 edge가 가져야 하는 값이 된다.
  • 업데이트 된 값과 기존의 값과의 차이를 표현하면 다음과 같다.
left edge 변동량 = (MAX[i] - w[i] * 2 - MAX[i * 2 + 1];
right edge 변동량 = (MAX[i] - w[i] * 2 - MAX[i * 2 + 2];
  • 위의 둘을 더해서 기존의 w를 모두 더해둔 sum에 추가해주면 된다.

코드

#include <iostream>

using namespace std;

int k, n, m, sum, w[2 << 21], MAX[2 << 21];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> k;
    n = (2 << k) - 2;
    m = (2 << (k - 1)) - 2;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        sum += w[i];
    }
    for(int i = n; i >= 0; i--) MAX[i] = w[i] + max(MAX[i*2 + 1], MAX[i*2 + 2]);
    for(int i = 0; i <= m; i++) sum += (MAX[i] - w[i]) * 2 - MAX[i * 2 + 1] - MAX[i * 2 + 2];
    cout << sum;
}

느낀점

  • acm-icpc 문제임에도 나름 순탄하게 풀어냈다..!
  • 내심 뿌듯한 순간이었다! 내일부터 본격적으로 화이팅해보자!