[코드트리] n개의 점 중 m개 고르기

https://www.codetree.ai/missions/2/problems/choose-m-out-of-n-points?&utm_source=clipboard&utm_medium=text

 

🔷 나의 구현 스케치

backtracking으로 n개의 점들 중 m개를 선택한다. 선택된 m개의 점들 중 거리가 가장 먼 점들의 길이를 계산한다. 모든 조합의 가장 먼 점들의 길이 중 최소를 구한다.

1) choose(index,cnt) 를 통해 n개 중에 m개 선택하는 모든 조합을 만든다.

2) m개가 선택되면 cal_dist() 함수를 통해 두 점 사이의 거리의 최대를 구한다.

3) ans = min(ans,cal_dist()) 는 모든 조합의  cal_dist() 값 중 최솟값으로 업데이트한다.

 

🔷  나의 구현 코드

n,m = map(int,input().split())
spot = [list(map(int,input().split())) for _ in range(n)]

def cal_dist():
    global choice
    max_dist = -1
    for i in range(len(choice)):
        for j in range(i, len(choice)):
            distance = (choice[i][0]-choice[j][0])**2 + (choice[i][1]-choice[j][1])**2
            max_dist = max(max_dist, distance)
    return max_dist
            
def choose(index,cnt):
    global ans, choice
    if cnt == m:
        ans = min(ans,cal_dist())
        return
    if index == n:
        return
    #not choose
    choose(index+1,cnt)
    #choose
    choice.append(spot[index])
    choose(index+1,cnt+1)
    choice.pop()

ans = 10000
choice = []
choose(0,0)
print(ans)