3119번 - 울타리 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 607 | 106 | 67 | 22.945% |
문제
상근이는 집 옆에 나무 울타리를 만들고 있다. 나무 울타리는 직사각형 나무판을 땅에 꽂아서 만든다.
울타리를 만들다보니 점점 흥이 났고, 상근이는 울타리 계획을 까먹고 마구 나무판을 꽂았다. 울타리를 완성한 후 뿌듯해하면서 울타리를 본 상근이는 대혼란에 빠졌다. 나무판을 겹쳐서 꽂기도 했고, 심지어 울타리 중간에 구멍도 있었기 때문이었다.
예제를 그림으로 나타낸 것이다. 굵은 선이 스카이라인이다.
아직 상근이는 울타리를 보고 충격에 빠진 상태이다. 이미 완성된 울타리가 마음에 들었기 때문에, 똑같은 모양의 울타리를 더 적은 수의 나무판을 이용해서 만들려고 한다.
똑같은 모양의 울타리란 스카이라인이 같은 울타리를 말한다.
어떤 나무판자를 남겨야 똑같은 모양의 울타리가 되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 나무 울타리를 만드는데 사용한 나무판의 개수 N (1 ≤ N ≤ 100,000)이 주어진다.
다음 N개 줄에는 각 나무판의 정보 X, W, H가 주어진다. X는 상근이의 집에서부터 떨어진 거리, W와 H는 나무판의 너비와 높이이다. 모든 수는 109를 넘지 않는다.
나무판은 입력으로 주어진 순서대로 1번부터 N번이다.
출력
첫째 줄에 남아있는 나무판의 개수 B를 출력한다. 이때, B를 최소로 해야한다.
둘째 줄에는 어떤 나무판이 남아있는지 공백으로 구분해 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.
예제 입력 1
5 10 11 30 19 1 20 15 9 10 7 7 20 3 12 40
예제 출력 1
3 1 3 5
예제 입력 2
6 15 8 4 10 8 3 25 3 7 3 9 5 1 5 3 7 2 2
예제 출력 2
5 1 2 3 4 5
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Final Exam #1 1번
- 문제를 번역한 사람: baekjoon
- 문제의 오타를 찾은 사람: lovinix, project42da
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호