9474번 - 삼각 분할과 삼각형 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 53 | 23 | 20 | 44.444% |
문제
다각형의 삼각분할이란 다각형을 삼각형으로 나누는 꼭짓점을 연결하는 직선의 집합이다. 직선은 반드시 다각형 내부에 있어야 하며, 꼭짓점을 제외한 다른 곳에서 다른 직선과 교차하면 안 된다.
위의 그림에서 굵은 선은 다각형의 변을 나타내고, 가는 선은 삼각분할을 나타낸다. 꼭짓점이 n개인 다각형을 삼각분할하면 (n-2)개의 삼각형을 만들 수 있다.
한 꼭짓점에서 시작해 변을 따라 이동하면서 각 꼭짓점에 있는 삼각형의 개수를 나열한 것을 삼각형 개수 수열이라고 한다. 위의 그림에 나와있는 다각형의 삼각형 개수 수열은 아래와 같다. 가장 왼쪽 위에 있는 꼭짓점에서 시작한다.
- 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개의 양의 정수로 이루어진 삼각형 개수 수열이 주어졌을 때, 이러한 수열을 만드는 다각형이 존재하는지 안하는지를 구하는 프로그램을 작성하시오. 존재하는 경우에는 삼각형을 모두 출력한다.
입력
첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 테스트 케이스 번호 K이며, 두 번째 숫자는 수열의 길이 N (4 ≤ N ≤ 20)이다. 다음 N개의 숫자는 삼각형 개수 수열이다.
출력
입력으로 주어진 수열이 삼각형 개수 수열이 아닌 경우에는 테스트 케이스 번호 K와 알파벳 대문자 "N"을 출력한다.
올바른 경우에는 테스트 케이스 번호 K와 알파벳 대문자 "Y"를 출력한다. 다음 (N-2)개 줄에는 어떤 꼭짓점이 삼각형을 이루는지 한 줄에 하나씩 출력한다. 꼭짓점은 입력으로 주어진 순서대로 1번부터 시작하며, 사전순으로 정렬해서 출력한다. k < l < m이 한 삼각형이고, r < s < t가 다른 삼각형일 때, 아래 조건을 만족하면 첫 번째 삼각형이 두 번째보다 사전순으로 앞선다.
k<r OR (k==r AND l<s) OR (k==r AND l==s AND m<t)
예제 입력 1
4 1 6 1 3 1 3 1 3 2 6 1 3 2 2 1 3 3 12 1 2 3 2 1 6 1 2 3 2 1 6 4 20 1 2 3 2 1 6 1 2 3 2 1 6 1 3 2 2 1 3 1 2
예제 출력 1
1 Y 1 2 6 2 3 4 2 4 6 4 5 6 2 N 3 Y 1 2 12 2 3 12 3 4 6 3 6 12 4 5 6 6 7 8 6 8 9 6 9 12 9 10 12 10 11 12 4 N
출처
ICPC > Regionals > North America > Greater New York Region > 2013 Greater New York Programming Contest G번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호