[BOJ] ์ด์ง„ ํŠธ๋ฆฌ(13325)

[๋ฐฑ์ค€(BOJ)] ์ด์ง„ ํŠธ๋ฆฌ(13325) C++

๋ฌธ์ œ : BOJ_13325๋ฒˆ ์ด์ง„ ํŠธ๋ฆฌ

๋ฌธ์ œ ์„ค๋ช…

ํŠธ๋ฆฌ ์ˆœํšŒ

ํฌํ™”์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ๋‹ค๋ฃจ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
ํŠธ๋ฆฌ์˜ ๋†’์ด k๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ๋ณดํ†ต์˜ ํŠธ๋ฆฌ ๋ฌธ์ œ์™€๋Š” ๋‹ค๋ฅด๊ฒŒ ๋…ธ๋“œ์˜ ๊ฐ’์ด ์•„๋‹Œ ๊ฐ„์„ ์˜ ๊ฐ’์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ๋ฆฌํ”„ ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ ์ค‘ ์ตœ๋Œ“๊ฐ’์„ x๋ผ๊ณ  ํ•œ๋‹ค๋ฉด, ๊ฐ๊ฐ์˜ ๊ฐ„์„ ์— ์ตœ์†Ÿ๊ฐ’์„ ๋”ํ•˜์—ฌ ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ๋ฆฌํ”„ ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ฐ๊ฐ์˜ ๋ชจ๋“  ๊ฑฐ๋ฆฌ๋ฅผ x๋ฅผ ๋งž์ถฐ์ค˜์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.


Solution

๊ฑฐ๋ฆฌ๋ฅผ ๋งž์ถœ ๋•Œ ์ƒ์œ„ ๋…ธ๋“œ์˜ ๊ฐ„์„ ์—์„œ ๊ฐ’์„ ์ตœ๋Œ“๊ฐ’์œผ๋กœ ๋”ํ•ด์ค„์ˆ˜๋ก ์ตœ์ข… ๊ฑฐ๋ฆฌ๋“ค์˜ ๊ฐ’์ด ์ค„์–ด๋“ญ๋‹ˆ๋‹ค.
์žฌ๊ท€์˜ ๋ฐฉ์‹์„ ์ด์šฉํ–ˆ์Šต๋‹ˆ๋‹ค.
์šฐ์„  dfs๋ฅผ ์ˆœํšŒํ•˜์—ฌ ๊ฐ€์žฅ ๋จผ ๋ฆฌํ”„ ๋…ธ๋“œ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค
๊ทธ๋ฆฌ๊ณ  ๋‹ค์‹œ ๋ฆฌํ”„ ๋…ธ๋“œ๋ฅผ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค.
์ด๋•Œ, ๋ฆฌํ”„ ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ™๊ฒŒ ๋งž์ถ”๊ธฐ ์œ„ํ•ด ๊ฐ„์„ ์— ๋” ํ•ด์•ผ ํ•˜๋Š” ๊ฐ’์„ ๊ฐ๊ฐ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๊ฐ„์„ ์œผ๋กœ ๋‹ค์‹œ ๋ณด๋‚ด์ค๋‹ˆ๋‹ค.
์ด์ง„ ํŠธ๋ฆฌ์ด๊ธฐ ๋•Œ๋ฌธ์— ์˜ค๋ฅธ์ชฝ๊ณผ ์™ผ์ชฝ ๊ฐ’์ธ ๋‘ ๊ฐ’๋งŒ ๋“ค์–ด์˜ค๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
์˜ค๋ฅธ์ชฝ๊ณผ ์™ผ์ชฝ์˜ ์ตœ์†Ÿ๊ฐ’์„ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๊ฐ„์„ ์— ๋”ํ•ด์ฃผ์–ด์•ผ ๋งˆ์ง€๋ง‰์— ๊ฐ„์„ ์— ๋”ํ•ด์•ผ ํ•˜๋Š” ๊ฐ’์˜ ์ตœ์†Ÿ๊ฐ’์ด ๊ตฌํ•ด์ง€๋ฏ€๋กœ, ์™ผ์ชฝ ์˜ค๋ฅธ์ชฝ ๊ฐ„์„ ์ด ํ•„์š”ํ•œ ๊ฐ’ ์ค‘ ์ตœ์†Ÿ๊ฐ’์„ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๊ฐ„์„ ์— ๊ฐฑ์‹ ํ•ด ์ฃผ๊ณ , ๊ทธ ๊ฐ„์„ ์„ ๋‹ค์‹œ ์ž์‹ ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๊ฐ„์„ ์— ๊ฐฑ์‹ ํ•ด ์ฃผ๋Š” ๋ฐฉ์‹์œผ๋กœ ํ•ด๊ฒฐํ•˜์˜€์Šต๋‹ˆ๋‹ค.


Description

  • ๋…ธ๋“œ ์œ„์ฃผ๊ฐ€ ์•„๋‹Œ ๊ฐ„์„  ์œ„์ฃผ๋กœ ํ•ด๊ฒฐํ–ˆ์Šต๋‹ˆ๋‹ค.
  • ์ž์‹ ์˜ ์ž์‹ ๋…ธ๋“œ์˜ ๊ฐ„์„  ๋ฒˆํ˜ธ๋Š” ์ž์‹ ์˜ ๊ฐ„์„  ๋ฒˆํ˜ธ *2 +1, ์ž์‹ ์˜ ๊ฐ„์„  ๋ฒˆํ˜ธ *2 +2๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int k, edgeCnt, edgeSum;
vector<int> edge;
vector<int> minValue;
void dfs(int idx,int sum){
    if(idx*2+1<=edgeCnt) dfs(idx*2+1,sum+edge[idx*2+1]);
    if(idx*2+2<=edgeCnt) dfs(idx*2+2,sum+edge[idx*2+2]);
    edgeSum=max(edgeSum,sum);
}
int recursion(int idx,int sum){
    if(idx*2+1>edgeCnt || idx*2+2>edgeCnt) {
        return minValue[idx] = edgeSum-sum;
    }
    minValue[idx]=min(recursion(idx*2+1,(sum+edge[idx*2+1])),recursion(idx*2+2,(sum+edge[idx*2+2])));
    return minValue[idx];
}
void minFunc(int idx, int value){
    minValue[idx]-=value;
    edge[idx]+=minValue[idx];
    if(idx*2+1>edgeCnt || idx*2+2>edgeCnt) return;
    minFunc(idx*2+1,value+minValue[idx]);
    minFunc(idx*2+2,value+minValue[idx]);
}
int main(){
    cin >> k;
    for(int i =1; i<=k;i++){
        edgeCnt+=pow(2,i);
    }
    minValue.resize(edgeCnt+1);
    edge.resize(edgeCnt+1);
    for(int i=1;i<=edgeCnt;i++){
        cin >> edge[i];
    }
    dfs(1,edge[1]);
    dfs(2,edge[2]);
    recursion(1,edge[1]);
    recursion(2,edge[2]);
    minFunc(1,0);
    minFunc(2,0);
    int result=0;
    for(int i=1;i<=edgeCnt;i++) {
        result+=edge[i];
    }
    cout << result << '\n';
    return 0;
}