😋 문제 분석
N명의 사람이 존재하고, 종이 M번 울린다.
이 종을 들을 수 있는 범위 R이 존재하며,
종을 울릴 때마다 변한다. (R이 정확히 얼마인지는 주어지지 않음)
종을 울릴 때마다 사람들이 종을 들었는지의 여부가 주어지는데,
이게 가능한 데이터인지를 판단해야 된다.
✅ 문제 풀이
상식적으로 무조건 지켜져야 되는 조건을 생각해보자
우선 종이 울리면, 종에 가까운 사람부터 소리를 듣게 될 것이다
그래서 사람 A, B가 존재할 때, A가 종에 더 가깝다면,
A가 종소리를 못 들었을 때 B도 못 들어야 된다
B가 들었는데 A가 못 듣는 것은 불가능하다
이 논리를 중심으로 문제를 접근해보자
종의 범위인 R이 큰 순서로 울렸다고 가정해본다면
R이 작아지면 작아질 수록 1을 갖는 사람의 수가 점점 줄어들 것이다
그럼 R이 줄어드는 순서로 데이터를 정렬했을 때,
1이던 사람이 0이 되는 것은 정상이다
하지만 0이던 사람이 갑자기 1을 보이는 것은 가능한 경우라고 할 수 없다
이 논리로 코드를 작성해보자
우선 입력을 받는다.
val (N, M) = readLine().split(" ").map(String::toInt)
val B = List(N) { readLine().split(" ").map(String::toInt) }
...여기서 종 관련 데이터를 종소리를 들은 사람이 많은 순서로 내림차순 정렬한다
val B = List(N) { readLine().split(" ").map(String::toInt) }
.sortedByDescending { row -> row.sumOf { it } }이제 한명 한명씩 종 데이터를 탐색해나간다
R이 큰 순서대로 정렬이 되어 있기 때문에,
모든 사람들의 데이터는 1 -> 1, 1 -> 0, 0 -> 0의 경향만 보여야 한다
0 -> 1이 보이면 뭔가 잘못된 것이다
탐색하는 코드를 작성하자. 0 -> 1인 시점이 발견되면 NO를 출력한다.
...
for (j in 0 until M) {
for (i in 1 until N) {
if (B[i-1][j] < B[i][j]) { // 0 -> 1인 경우
print("NO")
return // 잘못된 거 찾으면 바로 끝
}
}
}
...
NO를 출력하지 않고 for문을 벗어나면 YES를 출력
...
print("YES")모순을 찾기 위해 데이터를 어떻게 이용할 것인지를 떠올리는 게
생각보다 어려운 문제였다
