3066번 - 브리징 시그널 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 600 | 465 | 435 | 81.157% |
문제
ACM(Advanced Chip Manufacture)이라는 회사의 수석 칩(chip) 설계자인 한승이는 고민에 빠져있다. 경로 설계자들의 잘못으로 두 개의 블록의 포트를 연결하는 칩 위의 시그널들이 서로 교차하게 만들어졌다. 이 시점에서 경로 설계를 다시 하는 것은 비용이 너무 많이든다. 그 대신 엔지이너들은 교차하는 시그널들을 브리징 하기로 했다. 브리징은 시그널이 서로 교차하는 경우 하나의 시그널이 다른 시그널과 접촉하지 않도록 수직으로 띄우는 작업이다. 하지만 브리징은 어려운 작업이므로 가능하면 적은 수의 시그널만 브리징 해야한다. 실리콘 표면에서 서로 교차하지 않고 연결될 수 있는 최대 시그널의 개수를 찾는 프로그램을 작성하시오.
 |
 |
| 그림 1. 문제가 생긴 두 개의 블록의 포트와 포트를 연결하는 시그널 | 그림 2. 최대 세 개의 시그널이 서로 교차하지 않고 연결될 수 있다. 점선으로 표시된 시그널은 브리징 해야한다. |
두 개의 블록의 포트는 1번부터 N번까지 위에서 아래로 번호가 매겨져 있다. 각 포트는 다른 블록의 한 포트와 연결된다.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블록의 포트와 연결되어야 하는 오른쪽 블록의 포트 번호 ki(1 ≤ ki ≤ N)가 한 줄에 하나씩 N개 주어진다. 즉, i+1번째 줄에는 왼쪽 블록의 i번 포트와 연결되어야 하는 오른쪽 블록의 포트 번호가 주어진다.
출력
각 테스트 케이스에 대해 서로 교차하지 않고 연결될 수 있는 최대 시그널의 개수를 한 줄에 하나씩 출력한다.
예제 입력 1
3 6 4 2 6 3 1 5 10 2 3 4 5 6 7 8 9 10 1 9 5 8 9 2 3 1 7 4 6
예제 출력 1
3 9 4
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2003 A번
- 문제의 오타를 찾은 사람: doju
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호