다각형의 삼각 측정은 다각형을 삼각형으로 나누는 정점사이의 선들을 적절히 긋는 것으로 구할 수 있다. 정점 사이의 선들은 다각형 내부에 있어야 하며 정점을 제외하고는 서로 만나지 않아야 한다.

아래 예를 보자.

위의 예에서 굵은 선은 다각형의 외곽선이고 가는 선은 삼각측정을 위하여 그은 정점사이의 선들이다.

K개의 정점을 가진 다각형에서 나올 수 있는 삼각형의 개수는 K-2개이다.

삼각측정을 위하여 간선을 적절히 그은 후 삼각형 개수 수열을 구할 수 있다. 위 예에서 다각형 A의 삼각형 개수 수열은 다각형의 맨 위 왼쪽 정점을 시작으로 시계방향으로 진행하면서 정점에서 만들어지는 삼각형의 개수를 나열하면 된다. 다각형 A, B, C의 삼각형 개수 수열을 만들어 보면 아래와 같다.

A : 1 3 1 3 1 3 B : 2 2 1 4 1 2 C : 1 2 3 2 1 6 1 2 3 2 1 6

N 개의 정수로 입력된 수열을 입력받아 삼각형 개수 수열로 가능한지, 불가능한지 판별하는 프로그램을 작성하시오. 가능하다면 구성된 삼각형을 사전편집상 순서로 출력하는 프로그램을 작성하시오.

#2784 upload 6 done 3 how_to_reg 3

삼각형 개수 수열 timer 1s memory 32MB

#2784

삼각형 개수 수열 1s 32MB