시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 14 | 5 | 4 | 33.333% |
그래프를 주어진 제약조건을 만족하도록 평면상에 그리는 것은 VLSI에서 회로를 배선하거나 정보 시스템의 구조를 다이어그램으로 나타내어 분석하는데 이용된다. 이 문제에서는 주어진 이진트리(binary tree)를 다음 조건을 만족하도록 이차원 격자구조에 그리는 문제를 고려한다.
예를 들어, 다음은 주어진 이진트리를 위의 제약 조건을 만족하도록 그린 것이다.
왼쪽부터 이진트리, 그리기-1, 그리기-2, 그리기-3이다.
또, 위와 같이 이진 트리를 그릴 때는 그리기에 필요한 면적이 중요한 평가 요소가 된다. 어떤 그리기의 면적은 그리기에 필요한 이차원 격자의 가로크기와 세로크기를 곱한 값이다. 그러므로, 위의 그림에서 <그리기-1>의 면적은 16이며 <그리기-2>와 <그리기-3>의 면적은 15이다. 이진 트리가 주어질 때 위의 제약 조건을 만족하는 그리기 중 면적을 최소로 하는 그리기의 면적을 출력하는 프로그램을 작성하시오.
입력의 첫째 줄에는 이진트리의 정점수를 나타내는 n이 주어진다(1 ≤ n ≤ 100). 둘째 줄에는 n개의 정수로 구성된 수열이 주어진다. 주어지는 정수 수열은 이진트리를 전위(preorder) 순회한 순서가 1, 2, 3, . . . ,n 이라고 가정했을 때, 그 이진트리를 중위순회한 순서를 나타낸다. 정수 사이에는 빈칸이 하나 있다. 올바른 입력만 주어진다고 가정한다.
첫 줄에 최소 면적을 출력한다.
9 4 3 5 2 6 1 8 7 9
12