24366번 - КЛЕТКИ
24366번 문제의 조건은 '비둘기 간의 최소 간격이 최댓값이 되도록 배열한다' 하나뿐입니다.
그러나, 해당 조건밖에 없다면 답이 여러 개가 될 수 있다 생각합니다.
-
예를 들어,
새장이 15개, 비둘기가 5마리라 가정하고 비둘기를 O로 표시했을 때,
이렇게 경우의 수가 두 가지가 나올 수 있습니다.
첫 번째 경우의 수는,
비둘기 - 3칸 - 비둘기 - 3칸 - 비둘기 - 2칸 -비둘기 - 2칸 - 비둘기
두 번 쨰 경우의 수는,
비둘기 - 4칸 - 비둘기 -2칸 - 비둘기 - 2칸 - 비둘기 - 2칸 - 비둘기
첫 번째와 두 번째 모두,
최소 간격 d가 2로, 최댓값이 된다는 조건이 지켜졌음에도
첫 번째 경우에는 d가 2쌍, 두 번째 경우에는 d가 3쌍으로
문제에 대한 답이 전혀 다릅니다.
해당 문제에서는 첫 번째 경우에만 한해 답으로 인정하고 있습니다.
따라서 '최소 간격이 최댓값이 되도록 배열한다' 조건 외에도
'최대 간격이 최솟값이 되도록 배열한다' 라는 조건을 추가해야 한다 생각합니다.
댓글을 작성하려면 로그인해야 합니다.
kiwi_charm 4년 전 8
24366번 문제의 조건은 '비둘기 간의 최소 간격이 최댓값이 되도록 배열한다' 하나뿐입니다.
그러나, 해당 조건밖에 없다면 답이 여러 개가 될 수 있다 생각합니다.
-
예를 들어,
새장이 15개, 비둘기가 5마리라 가정하고 비둘기를 O로 표시했을 때,
이렇게 경우의 수가 두 가지가 나올 수 있습니다.
-
첫 번째 경우의 수는,
비둘기 - 3칸 - 비둘기 - 3칸 - 비둘기 - 2칸 -비둘기 - 2칸 - 비둘기
-
두 번 쨰 경우의 수는,
비둘기 - 4칸 - 비둘기 -2칸 - 비둘기 - 2칸 - 비둘기 - 2칸 - 비둘기
-
첫 번째와 두 번째 모두,
최소 간격 d가 2로, 최댓값이 된다는 조건이 지켜졌음에도
첫 번째 경우에는 d가 2쌍, 두 번째 경우에는 d가 3쌍으로
문제에 대한 답이 전혀 다릅니다.
-
해당 문제에서는 첫 번째 경우에만 한해 답으로 인정하고 있습니다.
따라서 '최소 간격이 최댓값이 되도록 배열한다' 조건 외에도
'최대 간격이 최솟값이 되도록 배열한다' 라는 조건을 추가해야 한다 생각합니다.