kiwi_charm   4년 전

24366번 문제의 조건은 '비둘기 간의 최소 간격이 최댓값이 되도록 배열한다' 하나뿐입니다.

그러나, 해당 조건밖에 없다면 답이 여러 개가 될 수 있다 생각합니다.

-

예를 들어,

새장이 15개, 비둘기가 5마리라 가정하고 비둘기를 O로 표시했을 때,

preview

이렇게 경우의 수가 두 가지가 나올 수 있습니다.

-

첫 번째 경우의 수는,

비둘기 - 3칸 - 비둘기 - 3칸 - 비둘기 - 2칸 -비둘기 - 2칸 - 비둘기

-

두 번 쨰 경우의 수는,

비둘기 - 4칸 - 비둘기 -2칸 - 비둘기 - 2칸 - 비둘기 - 2칸 - 비둘기

-

첫 번째와 두 번째 모두,

최소 간격 d가 2로, 최댓값이 된다는 조건이 지켜졌음에도

첫 번째 경우에는 d가 2쌍, 두 번째 경우에는 d가 3쌍으로

문제에 대한 답이 전혀 다릅니다.

-

해당 문제에서는 첫 번째 경우에만 한해 답으로 인정하고 있습니다.

따라서 '최소 간격이 최댓값이 되도록 배열한다' 조건 외에도

'최대 간격이 최솟값이 되도록 배열한다' 라는 조건을 추가해야 한다 생각합니다.

댓글을 작성하려면 로그인해야 합니다.