9335번 - 소셜 광고 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 366 | 135 | 88 | 39.640% |
문제
진욱이는 새로운 소셜 네트워킹 회사를 만들기로 결심했다. 하지만 기존의 페이스북 이나 트위터 같이 인기있는 소셜 네트워크 서비스는 이미 수십억의 사용자를 가지고 있고, 진욱이는 이들과 경쟁에서 승리하는 유일한 방법은 다른 소셜 네트워크가 가지고 있지 않은 새로운 기능을 포함하는 것이라 생각했다.
진욱이는 광고주에게 값싼 방법으로 광고비를 청구할 방법을 생각해냈다. 광고주는 어떤 사용자의 담벼락에 광고를 나타낼지 고르고 선택된 사용자의 광고비만 지불하면 된다. 광고가 사용자의 담벼락에 게시되었을 때, 사용자의 친구들 모두와 자기 자신은 그 광고를 볼 수 있다. 이러한 방식으로 더 많은 사용자들에 광고를 알리기 위해 광고주는 적은 수의 광고비용만 지불하면 된다.
해빈이는 진욱이의 소셜 네트워크에 광고를 게시하고 싶어한다. 해빈이는 이미 사용자들의 "친구 목록" 을 가지고 있으며 이 그룹의 모든 사용자들이 광고를 보기 위해서 해빈이가 특정 사용자들의 담벼락에 게시해야 하는 최소의 광고 수를 구하여라.
진욱이의 소셜 네트워크에서는 A와 B가 친구이면 B도 A와 친구이다.
입력
입력은 여러개의 테스트 케이스로 이루어져 있다. 첫째 줄은 테스트 케이스를 나타낸다. 각각의 케이스마다 전체 사용자의 수 n (1 ≤ n ≤ 20) 이 주어진다. 다음 n개의 줄에는 친구의 목록이 입력으로 주어지는데 각각의 줄은 친구의 수 d (0 ≤ d < n) 가 먼저 입력으로 주어지고 뒤이어 d개의 친구 번호가 주어진다. i번째 줄은 i번째 사용자를 뜻하며 자기 자신이 친구일 수는 없다.
출력
각각의 케이스 마다 모든 사용자들이 광고를 볼수 있도록 해빈이가 게시하여야 하는 최소의 광고 수를 출력한다.
예제 입력 1
2 5 4 2 3 4 5 4 1 3 4 5 4 1 2 4 5 4 1 2 3 5 4 1 2 3 4 5 2 4 5 2 3 5 1 2 2 1 5 3 1 2 4
예제 출력 1
1 2
출처
ICPC > Regionals > North America > Rocky Mountain Regional > 2013 Rocky Mountain Regional Contest G번
- 잘못된 번역을 찾은 사람: chogahui05
- 문제를 번역한 사람: lll4592
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호