[코드트리 조별과제] n개의 점 중 m개 고르기

https://www.codetree.ai/missions/2/problems/choose-m-out-of-n-points

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제는 사이트 들어가시면 볼 수 있습니다.

문제 설명
이 문제는 주어진 n개의 점 중에서 m개의 점을 선택하여 조합을 만든 후, 각 조합에서 두 점 사이의 유클리드 거리의 제곱의 최댓값을 구합니다. 이때, 가능한 모든 조합에 대해 최댓값을 구한 뒤, 이 최댓값들 중에서 최솟값을 구하는 문제입니다.

입력

• 첫 줄에 n과 m이 주어집니다. n은 점의 개수, m은 선택할 점의 개수를 의미합니다.
• 다음 n줄에 걸쳐 각 점의 좌표 (x, y)가 주어집니다.

코드 설명

1. 입력처리 

n,m = map(int,input().split())  # n개 중 m개 선택
dots = []
for _ in range(n):
    x,y = map(int,input().split())
    dots.append((x,y)) # x,y 입력받음

여기서 n개의 점을 입력받아 dots 리스트에 저장합니다.


2. 초기화

result = 0
ans = 0
result1 = 20001

 

• result: 각 조합에서 계산된 두 점 사이의 거리의 제곱 중 최대값을 저장합니다.
• ans: 두 점 사이의 유클리드 거리의 제곱을 계산하는데 사용됩니다.
• result1: 모든 조합의 최대값들 중 최솟값을 저장합니다. 주어진 구간에 의한 최대값보다 크게 설정하였습니다.

3.조합을 선택하고 거리 계산

 

def select(start, cnt, arr, tmp):
    global result, ans, result1
    if cnt == m:
        result = 0
        for i in range(len(tmp)):
            for j in range(i+1, len(tmp)):
                ans = (tmp[i][0] - tmp[j][0])**2 + (tmp[i][1] - tmp[j][1])**2
                result = max(result, ans)
        result1 = min(result1, result)
        return

    for i in range(start, len(arr)):
        tmp.append(arr[i])
        select(i+1, cnt+1, arr, tmp)
        tmp.pop()

 

• select 함수는 start부터 시작하여 m개의 점을 선택하는 조합을 생성합니다.
• 각 조합이 선택되면, tmp 리스트에 저장된 점들 사이의 거리를 계산하여 result에 그 중 최대값을 저장합니다.
• 모든 조합을 고려한 후, result1에 현재까지의 최소 result 값을 갱신합니다.
• tmp.pop()을 통해 마지막에 추가된 점을 제거하여 다음 조합을 고려할 수 있도록 합니다.

4. 결과 출력

select(0, 0, dots, [])
print(result1)​

 
조합을 생성하고, 필요한 계산을 수행한 후 최종적으로 result1에 저장된 최솟값을 출력합니다.

중복 방지: select 함수의 start 인덱스와 cnt를 통해 조합에서 중복이 발생하지 않도록 합니다. 이를 통해 조합이 동일한 순서로 반복되는 것을 방지합니다.

전체코드

n,m = map(int,input().split())
dots = []
for _ in range(n):
    x,y = map(int,input().split())
    dots.append((x,y))

result=0
ans =0
result1=20001

def select(start,cnt,arr,tmp):
    global result,ans,result1
    if cnt == m :
        result =0
        for i in range(len(tmp)):
            for j in range(i+1,len(tmp)):
                ans = (tmp[i][0]-tmp[j][0])**2 + (tmp[i][1] -tmp[j][1])**2
                result = max(result,ans)
        result1 =min(result1,result)          

    for i in range(start,len(arr)):
        tmp.append(arr[i])
        select(i+1,cnt+1,arr,tmp)
        tmp.pop()


select(0,0,dots,[])
print(result1)