[c++] BOJ 12888 :: 완전 이진 트리 도로 네트워크

문제

완전 이진 트리 도로 네트워크 문제 바로가기

BOJ 나라는 도시와 두 도시를 연결하는 도로로 이루어져 있다. 이 나라의 도로 네트워크는 완전 이진 트리의 형태를 가진다.

수빈이는 BOJ 나라의 도로 네트워크 트리의 높이 H를 알고 있다. 트리의 높이를 안다면, 도시의 개수와 도로의 개수도 구할 수 있다. 트리의 높이가 H인 경우에 도시의 개수는 2(H+1)-1개 이고, 도로의 개수는 2(H+1)-2개가 된다.

아래 그림은 H = 2일 때, 그림이다.

수빈이는 도로 네트워크에 차를 보내려고 한다. 모든 차는 시작 도시와 도착 도시가 있으며, 같은 도시를 두 번 이상 방문하지 않는다. 차의 시작 도시와 도착 도시가 같을 수도 있다.

모든 도시를 방문한 차의 개수가 모두 1개가 되기 위해서, 수빈이가 차를 최소 몇 대를 보내야 하는지 구하는 프로그램을 작성하시오.

 

풀이

 

위와 같은 트리가 있을 때, 해당 문제는 어떤 점화식으로 이루어져 있을까?

첫번째 방법은 한 자동차가 루트를 가로지르는 가장 긴 길이의 도로를 가는 것이다.

h 높이의 트리에서 문제의 답을 T(h)라는 수식으로 나타낼 수 있다고 가정하자. 이렇게 되면 빨간색과 주황색은 항상 필요한 차의 개수이므로 3개를 기본으로 하고, T(h-2)부터 T(1)까지 2를 곱하면서 계속 더해주면 된다.

하지만 h가 높아감에 따라서 완전 이진 트리이므로 똑같은 규칙이 반복되고, 이를 점화식으로 나타낼 수 있는데 T(i) = T(i-1) + T(i-2)*2이다.

 

 

두 번째로는 위의 한 트리와 아래의 두 트리로 나누는 방법이다.

이렇게 나타내었을 때 j를 빨간색으로 표시한 트리의 h라고 생각해보자. j는 i-j가 1이 될 때까지 즉, 아래의 주황색 트리 높이가 1이 될 때까지 진행되며, 시작은 빨간색 트리가 0일 때부터 시작한다.

점화식은 다음과 같다.

 

따라서 해당 문제는 첫번째 방법과 두번째 방법을 모두 시행하면서 가장 작은 값을 찾아내면 된다. 입력 값이 적을 때는 첫번째 방법이 무조건 정답인 것처럼 보이지만, 입력 값이 커지게 되면 그렇지 않을 수도 있다.

또한, 두번째 방법은 트리의 높이만큼 진행해야 하고 모든 높이의 트리에 대해 정답을 미리 구해놓으므로 O(n^2)이지만 높이가 60이 최대이므로 충분하다.

 

코드

#include <iostream>
#include <math.h>

using namespace std;


int main() {
    long long powArr[61];
    for (int i = 1; i < 61; i++) {
        powArr[i] = pow(2, i);
    }

    long long result[61] = { 1,1,3 };

    for (int i = 3; i < 61; i++) {
        result[i] = result[i - 1] + result[i - 2] * 2;
        for (int j = 1; i-j > 0; j++) {
            long long tmp = result[j - 1] + result[i - j] * powArr[j];
            if (tmp < result[i])
                result[i] = tmp;
        }
    }

    int h; cin >> h;
    cout << result[h];
}

 

개선

• 두 번째 방법은 반복적인 패턴이 나타나기 때문에 시간을 줄일 수도 있겠지만, 시간이 이미 0ms이기 때문에 딱히 줄이지 않아도 될 것 같다.
• 입력을 먼저 받고 입력까지의 result 배열만 채우는 것도 시간을 줄일 수 있다.

 

결과

아이디	메모리	시간	코드 길이
gmldms784	2208	0	730