제야의 종
면접 대비시간 제한1초메모리 제한512 MB
각 종소리를 누가 들었는지 나타낸 N×M 격자가 주어질 때, 각 타종의 반경 R을 적절히 정해 이 패턴을 만들 수 있는지 판정한다.
문제
제야의 종 타종은 한 해의 끝과 새해의 시작을 알리는 행사이다. 이 행사에서는 보신각의 종을 여러 번 친다.
제야의 종을 쳐서 나는 종소리는 종으로부터 특정 거리 R 이내에 있는 사람은 모두 들을 수 있고, R보다 멀리 있는 사람은 모두 들을 수 없다. 정치인, 연예인 등 유명 인사가 돌아가며 타종하기 때문에 종을 칠 때마다 R의 값은 바뀐다.
N명의 사람이 있고, 2019년 12월 31일 밤에 열린 제야의 종 타종에서 총 M번 종을 쳤다고 하자. M번의 타종이 진행되는 동안 사람들은 종소리에 집중하느라 움직이지 않는다.
N명의 사람 각각이 M번의 타종을 들었는지 여부가 주어졌을 때, 실제로 가능한 상황인지 판별하여라.
입력
첫 줄에 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 100)이 주어진다.
i+1(1 ≤ i ≤ N)번째 줄에는 M개의 정수 a**i,1, a**i,2, ..., a**i,M 이 주어지는데, a**i,j가 1이면 사람 i가 j번째 타종을 들었음을, 0이면 듣지 못했음을 의미한다.
출력
실제로 가능하다면 YES, 아니면 NO를 출력하라.