akim9905   5년 전

문제에서 언급된 3번 조건은 다음과 같습니다.

"3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다."

그런데, 해당 경우를 만족하지 않으면서 최적해인 경우는 존재하지 않습니다.

만약 어떤 마을 A가 어떤 우수마을과도 인접하지 않고, 그게 최적해라고 가정을 하면,

A를 선택했다면 반드시 최적해보다 값이 커질 것이니 최적해라는 가정에 모순이 발생합니다.

(상식적으로 주민수는 0명 이상일 것이고, 문제 또한 10,000 이하라고만 할 뿐 별다른 조건이 없기 때문에 음수인 상황은 고려하지 않았습니다.)

따라서 최적해는 늘 3번 조건을 만족하므로, 삭제해도 되는 조건이라고 생각합니다.

djm03178   5년 전

문제의 조건을 최대한 타이트하게 해야 할 필요는 없습니다.

불필요한 조건에 의해 문제를 푸는 사람이 일부러 헷갈리게 하도록 의도한 것일 수도 있고, 이것도 문제의 일부입니다. 해당 문장이 없어지면 생각해봐야 할 거리가 적어지기 때문에 체감 난이도 자체가 변하게 됩니다.

startlink   5년 전

문제없습니다.

blueapple99   5년 전

저도 3번 지문 때문에 문제가 더 어려웠는데 생각을 깊게 하고 보니 1번을 통해 3번을 유추하는 것도 이 문제의 좋은 의도 같아요!

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