백준 30466 - 우정은 BFS처럼, 사랑은 DFS처럼 (C++)

문제

• 문제 링크

  
   BOJ 30466 - 우정은 BFS처럼, 사랑은 DFS처럼 
  

• 문제 요약

$1$부터 $N$까지 번호가 메겨진 $N$개의 정점으로 이루어진 트리를 구하고자 한다.
$1$번 정점을 시작으로 $DFS$와 $BFS$를 수행할 때, $d_i$, $b_i$를 각각 $DFS$, $BFS$에서 $i$번 정점에 방문한 순서라고 정의하자.

이때, $\sum_{i=1}^{N}{|d_i-b_i|}$ 을 최대로 하는 트리를 만들어보자.


• 제한

TL : $1$ sec, ML : $1024$ MB




$3 ≤ N ≤ 200,000$

각 탐색에서, 순회 후보가 여럿인 경우에는 번호가 더 작은 정점을 먼저 방문한다.

알고리즘 분류

• 트리 (trees)
• 해 구성하기 (constructive)

풀이

적당한 $N$에 대해 이런 저런 트리 모양을 그려봤는데, 항상 식의 최댓값을 낼 것 같은 트리의 모양이 보였다.

$m = ⌊$$\frac{N}{2}⌋$ 라 하자.

간선을 {$1, 2$}, {$2, 3$}, ... , {$m, m+1$} 로, 즉 $m$개의 정점을 $1$번 정점으로부터 일렬로 이어준다.

나머지 $n - m - 1$개의 정점은, $1$번 정점을 둘러싼다.

이 경우, 계산해보면 알겠지만 $\sum_{i=1}^{N}{|d_i-b_i|}$ = $2*(m - 1) * (n - m - 1)$ 이고 이 값이 바로 최댓값이다.

전형적인 $Proof$ $By$ $AC$였는데, 엄밀한 증명은 어찌해야 할까?

전체 코드

#include<bits/stdc++.h>
 
int main()
{
    int n; std::cin >> n;
    int m(n >> 1), i(1);
 
    std::cout << (long long)(m - 1) * (n * 2 - m * 2 - 2) << '\n';
    for (; m--; i++) printf("%d %d\n", i, i + 1);
    for (i += 1; i <= n;) printf("1 %d\n", i++);
}

comment

끝