시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 764 | 271 | 199 | 40.530% |
"마, 내가 누군지 아나? 저커버그가 내 후임이다."
준원이는 저커버그와 함께 페이스북을 만들던 리즈시절을 회상하곤 한다... 저커버그가 페이스북을 다 만들기 직전, 바로 그 순간 저커버그에게 급똥이 찾아왔다. 그는 마지막 남은 기능 하나를 준원이에게 맡겼고, 그 기능이 바로 '함께 아는 친구' 기능이었다.
페이스북의 사용자는 총 N명이고, 각 사용자는 1번에서 N번까지로 번호 붙어 있었다. 준원이는, 사용자의 친구관계에 대한 정보가 모두 주어졌을 때,
"a번 사용자, b번 사용자와 공통적으로 친구 관계인 사용자의 수"
를 묻는 Q개의 질문에 차례로 답해야 했다.
준원이는 천하코일제딩대회 참가자 여러분에게 이 기능을 외주 맡겼다. 여러분이 이 기능을 대신 구현하면, 준원이는 여러분이 천하코일대딩제회에서 맞은 문제를 몰래 하나 늘여주겠다고 한다. 어떤가?
첫째 줄에, 사용자의 수를 나타내는 정수 N이 주어진다.
이후 N개의 줄에 걸쳐, 각 사람의 친구관계를 나타내는 길이 N의 문자열이 N개 주어진다. i번째 줄의 j번째 문자는, i번 사용자가 j번 사용자와 친구일 때에 1
, 아닐 때에 0
이다.
이후, 질문의 개수를 나타내는 정수 Q가 주어진다.
이후 Q개의 줄에 걸쳐, 질문을 나타내는 두 정수 a와 b가 공백을 사이에 두고 주어진다.
Q개의 줄에 걸쳐, 각 질문에 대한 답을 나타내는 정수를 하나씩 차례대로 출력한다.
4 0110 1011 1100 0100 3 2 4 1 3 1 4
0 1 1
예제에서, 1, 2번 사용자, 1, 3번 사용자, 2, 3번 사용자, 2, 4번 사용자는 서로 친구이다.
이 때,
입출력 양이 많다. 느린 입출력 함수를 쓰면 입력 받는 데에 걸리는 시간만으로 시간 초과가 발생할 수 있으므로 유의하라.
cin
, cout
함수를 가급적 쓰지 말고, scanf
, printf
함수로 입출력을 진행하는 편이 좋다.Scanner
클래스 대신, BufferedReader
클래스를 사용하여 입력받는 편이 좋다.input
함수를 쓰는 대신, import sys
를 코드의 앞 부분에서 선언하면 같은 역할을 하는 더 빠른 함수인 sys.stdin.readline
을 쓸 수 있다.High School > 선린인터넷고등학교 > 제4회 천하제일 코딩대회 F번