니노니나니

https://www.acmicpc.net/problem/9347문제준규는 화원을 운영중이다. 준규는 엄청난 가치를 지닌 대마꽃를 M개의 행과 N개의 열을 가진 토지에 경작하는데 진욱이가 자꾸 훔쳐가서 고민에 빠졌다. 준규는 진욱이가 훔쳐가지 못하게 꽃 주변을 울타리로 둘러쌓다. 하지만 시간이 지나면서 울타리 몇개가 부서졌다. 진욱이는 이때를 틈타 다시 꽃을 훔지려고 한다.아래 보이는 그림은 11행 12열의 화원을 나타낸다. 0은 울타리가 없거나 꽃이 심어져 있는 부분을 나타내고 1은 울타리가 있는 곳을 나타낸다. 화원에 들어 오려면 노란색 부분부터 들어와야 한다.진욱이가 꽃을 훔치러 화원에 들어왔다. 울타리를 요리조리 피해서 들어가는데 이때 상, 하, 좌, 우로 밖에 이동할 수 없다. 진욱이는 파괴적 ..

문제각 에지에 양수인 가중치가 부여된 높이가 $k$인 포화이진트리가 주어져 있다. 높이 $k$인 포화이진트리는 $2^k$개의 리프를 포함하여 ($2^{k+1}-1$)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 이 문제에서는, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같도록 하고, 또한 에지 가중치들의 총합을 최소화 하려고 한다.예를 들어, 그림 1(a)에 있는 높이 2 인 포화이진트리를 살펴보자. 에지 옆에 있는 수는 그 에지의 가중치를 나타낸다. 이 경우에 대한 답이 그림 1(b)에 나타나 있다. 즉, 루트에서 모든 리프까지의 거리가 5 이고, 에지 가중치들의 총합은 이 경우에 가능한 최솟값인 ..