C++로 트리의 두 정점 간 차수 곱의 합을 최대화하는 방법

이 문제는 주어진 정수 N을 이용해 트리를 구성하고, 모든 순서쌍 (x, y)에 대해 degree(x) × degree(y)의 합이 최대가 되도록 만드는 것입니다. 단, x와 y는 서로 달라야 합니다.

예제

입력: N=5

출력: 50

설명:

위 트리에서 각 노드의 차수(degree)는 다음과 같습니다.

1번 노드의 차수 = 1
2번 노드의 차수 = 2
3번 노드의 차수 = 2
4번 노드의 차수 = 2
5번 노드의 차수 = 1

모든 순서쌍 (x, y)에 대한 차수의 곱은 다음과 같이 계산됩니다.

1번 노드 = 1×2 + 1×2 + 1×2 + 1×1 = 7
2번 노드 = 2×1 + 2×2 + 2×2 + 2×1 = 12
3번 노드 = 2×1 + 2×2 + 2×2 + 2×1 = 12
4번 노드 = 2×1 + 2×2 + 2×2 + 2×1 = 12
5번 노드 = 1×2 + 1×2 + 1×2 + 1×1 = 7
합계 = 50

또 다른 예시로, N=7인 경우 출력값은 122가 됩니다.

접근 방식

프로그램에 적용된 핵심 아이디어는 다음과 같습니다.

트리에 있는 모든 노드 차수의 총합은 (2 × N) − 2입니다. 여기서 N은 트리의 노드 수입니다. 합을 최대화하려면 리프 노드(차수가 1인 노드)의 개수를 최소화해야 합니다.
Max() 함수 안에서 sum 변수를 0으로 초기화한 뒤, 중첩 반복문을 사용해 x와 y를 1부터 N까지 순회합니다.
반복문 내부에서 먼저 x == y인지 확인하고, 같다면 continue 문으로 건너뜁니다.
x와 y의 차수를 기본적으로 2로 초기화합니다. 그런 다음 if 문으로 해당 노드가 루트 노드(1)이거나 리프 노드(N)인지 검사하고, 해당되면 차수를 1로 설정합니다.
마지막으로 반복문이 끝나기 전에 sum 변수에 degreeX × degreeY 값을 누적합니다.

여기서 중요한 점은, 선형 형태의 트리(경로 그래프)를 만들면 리프 노드가 딱 2개뿐이므로 나머지 모든 노드의 차수가 2가 되어 곱의 합이 최대화된다는 것입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int Max(int N){
    int sum = 0;
    for (int x = 1; x <= N; x++){
        for (int y = 1; y <= N; y++){
            if (x == y)
                continue;
            // 노드 x의 차수를 2로 초기화
            int degreeX = 2;
            // x가 리프 노드이거나 루트 노드인 경우
            if (x == 1 || x == N)
                degreeX = 1;
            // 노드 y의 차수를 2로 초기화
            int degreeY = 2;
            // y가 리프 노드이거나 루트 노드인 경우
            if (y == 1 || y == N)
                degreeY = 1;
            // sum 값 갱신
            sum += (degreeX * degreeY);
        }
    }
    return sum;
}
// 메인 함수
int main(){
    int N = 5;
    cout << Max(N);
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

이처럼 트리를 일직선 경로 형태로 구성하면 대부분의 노드가 차수 2를 가지게 되어, 모든 순서쌍의 차수 곱의 합이 최대가 됩니다.