hoyun293   2년 전

분명 저의 로직이 틀렸겠지만, 어떤 예외케이스가 있는지를 제 수준으로는 찾지 못하였습니다.

저는 먼저 각각의 치킨 가게에서 집들로부터 거리의 총합을 구한 뒤,  오름차순으로 정렬 한 뒤, 주어진 M개 만큼 치킨 가게를 선정하였습니다.

(집들로부터 가장 멀리있는 치킨 집을 폐쇠하기 위해)


그리고 각각의 집으로부터 주어진 M개의 치킨 가게중 가까운 치킨 집의 거리를 구하였습니다. (만약 M이 3일경우  3개의 치킨 집 중 가장 가까운 거리)

그리고 최종적으로 각각의 집으로부터 가장 가까운 치킨 거리를 더하였습니다.

브루트포스 방식으로 풀려고 시도하였습니다.

답변주시면 감사하겠습니다 ㅠ

klimmek55   2년 전

아래와 같은 경우에 안됩니다.

(5,1)과 (3,4)의 치긴집을 고르면 치킨 거리가 13인데,
(5,1) 치킨집에서 거리의 합보다 (4,3) 치킨집에서 거리의 합이 작아서 (4,3) 치킨집을 골라 15가 나오네요.

브루트포스라고 하면 보통 모든 경우를 다 확인하는걸 말하는데 이 코드는 그렇지 않네요.

hoyun293   2년 전

와... 감사합니다; 예외케이스  이걸발견하려고 했는데 생각이 도저히 안났는데 

감사합니다! 

그냥 모든 조합을 골라서 그중 가장 작은 치킨 거리를 고르는 방식으로 해야겠네요 

다시 한 번 감사드립니다 :)

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