문제풀이
- 기준점을 하나 잡고 다른 수들을 비교해 가면서 기준점과 같으면 A 리스트, 다르면 B 리스트에 넣는다.
- A, B 리스트 중에 현재 남아 있는 가짜 동전 개수(M)보다 size가 큰 리스트가 있으면 그 리스트 전체가 진짜 동전 집합이고, 나머지 리스트가 가짜 동전 집합이다.
- 아직 비교하지 않은 다음 기준점으로 넘어가서 1, 2를 반복하며 가짜 동전들을 찾는다.
주의사항
소요시간
25분
package AtCoder.ProblemList.Difficulty1300.Appraiser
fun main() {
val (N, M, Q) = readln().trim().split(" ").map(String::toInt)
val result = mutableListOf<Int>()
val A = mutableListOf<Int>()
val B = mutableListOf<Int>()
var start = 1
while (start <= N) {
var end = start + 1
A.add(start)
while (A.size <= (M - result.size) && B.size <= (M - result.size)) {
println("? $start $end")
if (readln().trim().toInt() == 0) A.add(end)
else B.add(end)
if (++end > N) break
}
if (end > N) {
if (result.isNotEmpty()) {
println("? ${result.first()} ${A.first()}")
if (readln().trim().toInt() == 0) result.addAll(A)
else result.addAll(B)
} else {
println("? 1 ${A.first()}")
if (readln().trim().toInt() == 0) result.addAll(B)
else result.addAll(A)
}
} else if (A.size > (M - result.size)) {
result.addAll(B)
} else {
result.addAll(A)
}
start = end
A.clear()
B.clear()
}
println("! ${result.joinToString(" ")}")
}