백준 15686번 치킨 배달

문제 설명

이번 문제는 좌표에 치킨 집과 가정 집이 있고 남길 치킨 집의 개수가 주어졌을 경우,

가정 집과 가장 가까운 치킨 집 사이의 거리를 치킨 거리라고 할 경우, 모든 가정 집의 치킨 거리의 합의 최소값을 구하는 문제입니다.

 

문제 풀이

아이디어

치킨 거리의 합의 최소값 구하는 방법

이번 문제는 각 가정집에서 치킨 집까지의 거리를 모두 구해야지만 최소값을 구할 수 있습니다.

그리고 남길 M개의 치킨 집 조합에 따라 각 가정집의 치킨 거리는 달라집니다.

그러므로 이번 문제는 모든 경우의 수를 다 살펴봐야지만 정답을 구할 수 있습니다.

-> 브루트포스 알고리즘

 

풀이

풀이 1.

각 치킨 집 중 m개의 조합을 구해서 각 조합의 치킨 거리를 구한 다음 비교하여 최소값을 구해냅니다.

->필자는 위의 방법을 사용해서 문제를 풀었습니다.

 

풀이 2.

각 치킨 집을 조합에 포함할 경우와 포함하지 않았을 때의 조합을 찾기 위해 백트래킹을 사용할 수 있습니다.

해당 치킨 집을 조합에 포함할 경우와 포함하지 않을 경우를 재귀를 통해 구현해볼 수 있습니다.

-> 백준 알고리즘 분류에 명시됨

 

 

해결

이번 문제는 브루트포스로 접근하기 전까지 최대한 고민해보다가 입력 N과 M이 비교적 작다는 것을 확인하고 파이썬의 조합 내장함수를 통해 풀 수 있었습니다.

 

문제 링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/15686.py