[SW Expert Academy] 1494 사랑의 카운슬러 (Python)

 

SW Expert Academy

 

- 문제 설명

• N마리의 지렁이가 있다. (N은 짝수) 지렁이를 2마리씩 소개팅을 시켜준다.
• 소개팅을 시키기 위해선 한 지렁이가 다른 지렁이에게 이동해야한다.
• 지렁이는 2차원 평면에서 이동하며 점 A에 있는 지렁이가 점 B에있는 지렁이에게 이동했다면
  벡터 AB가 된다.
• 모든 지렁이를 매칭시킨 후 나온 벡터를 모두 더한 후 그 벡터의 크기를 구한다.
  벡터의 크기 |V| = |(x, y)| = x*x + y*y

주의사항

각 벡터별 크기의 합을 구하는 것이 아닌 모든 벡터를 더한 후 (방향값 포함)
남은 하나의 벡터의 크기를 구하는 것

 

- 접근 방법

• 예시의 입출력을 확인하니 입력받은 값(x ,y)의 절반은 (-x, -y)로 바꾸어 x, y값을 각각 모두 더한 후
  벡터의 크기를 계산하였을 때 가장 작은 값을 출력하였다.
• 입력받은 총 개수(N)의 절반만큼 음수로 바꿀 수 있도록 조합을 사용해 모든 경우의 수를 찾아
  반복하여 벡터의 크기가 가장 작은 경우를 찾도록 코드를 작성했다.

 

- 입출력 예시

 

- 코드

from itertools import combinations

T = int(input())
for tc in range(1, T+1):
    n = int(input())
    num = [tuple(map(int, input().split())) for _ in range(n)]
    t1 = [i for i in range(n)]      # 0 ~ n-1 까지의 리스트
    
    # 조합을 사용해 입력의 개수 중 절반을 추출하는 경우의 수 저장
    test = list(combinations(t1, n//2))
    # 경우의 수만큼 반복
    for i in range(len(test)):
        x = y = 0       # 값 초기화
        # num의 길이 n만큼 반복
        for j in range(n):
            # 인덱스 j가 현재 경우의 수 목록인 test[i]에 포함되어 있다면
            if j in test[i]:
                # x, y에 각 원소를 마이너스
                x -= num[j][0]
                y -= num[j][1]
            else:
                # 아니라면 각 원소를 플러스
                x += num[j][0]
                y += num[j][1]
        # 첫번째 반복에서 결과값을 최소값에 저장
        if i == 0:
            # 결과값은 x의 제곱 + y의 제곱
            rlt_min = (x * x) + (y * y)
        rlt = (x * x) + (y * y)
        # 최소값 갱신
        rlt_min = min(rlt_min, rlt)

    print(f'#{tc} {rlt_min}')

 

성공은 했는데 메모리와 실행시간이 너무 높다
백준이었다면 실패했을 것 같다ㅠㅠ