[백준] 17371 이사

https://www.acmicpc.net/problem/17371

17371번: 이사

"가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균이 최소가 되는 좌표로 이사하려고 한다. "

가장가까운 편의시설까지의 거리 = 0 이어도 된다. 즉 편의시설에 집이 위치해도 되는 것이다.

그러면 가장 먼 편의시설까지의 거리가 최소가 되어야 한다.

따라서 각 좌표를 기준으로 하여 가장 긴 길이를 구하고, 긴 길이들 중 가장 짧은 길이를 구하면 된다.

 

<시간초과가 난 코드>

1.입력받을 좌표의 갯수 n

2.n번의 경우만큼 좌표를 입력받아 location리스트에 추가

3. 두 좌표의 길이를 구하는 함수length

4.(a,b)(a,c)(a,d)(a,e) // (b,a)(b,c)(b,d)(b,e) // (c,a)(c,b)(c,d)(c,e)// (d,a)(d,b)(d,c)(d,e) // (e,a)(e,b)(e,c)(e,d)

 n개의 좌표를 각각 기준점으로 해 길이를 n-1개씩 구해 distance리스트에 저장 

5. distance리스트 내 n 개의 리스트 중 가장 긴 길이를 구해 max_d리스트에 저장

6. max_d에서 가장 짧은 리스트의 원소를 찾아 출력

 

시간초과가 난 코드

import math
import sys


n = int(sys.stdin.readline())  #편의시설 갯수

location = []  # 편의시설의 위치를 n개 저장할 리스트
for i in range(n):
    a = list(map(int,input().split()))
    location.append(a)
# print(location)


def length(x,y,z,w):
    p = (x-z)**2 + (y - w) **2
    ans = math.sqrt(p)
    return ans

distance=[]
for i in range(n):
    b = []
    for j in range(n):
        if j != i:
            p = length(location[i][0],location[i][1],location[j][0],location[j][1])
            b.append(p)
    distance.append(b)
# print(distance)
# print(len(distance))

max_d = []
for i in range(n):
    for j in range (len(distance[i])):
        d = max(distance[i])
    max_d.append(d)
# print(max_d)


tt = []
for k in range(n):
    if (max_d[k]) == min(max_d):
        t = k
        tt.append(t)
        
kk = tt[0]
print(location[kk][0],location[kk][1])

리스트에 값들을 저장하는 경우 시간 복잡도가 매우 크기 때문에 시간초과가 난 것 같다. 

문제를 잘 읽어보면 1 < n <= 1000  이며  x와 y(-104 ≤ x, y ≤ 104) 이다.

따라서 가장 긴 길이가 될 수 있는 (10000,10000)와(-10000,-10000) 사이 거리를 변수best_length로 지정해주고 

맨 처음 가장 긴 길이 max_d를 0으로 지정 이때 max_d가 존재하는 인덱스를 max_d_l로 지정

입력한 좌표들을 2개씩 길이를 순서대로 길이를 구하면서 max_d를 갱신max_d< best_length인 경우 best_length를 max_d로 갱신이때 max_d의 위치를 통해 결과를 출력 

성공한 코드

import math
import sys


n = int(sys.stdin.readline())  #편의시설 갯수

location = []  # 편의시설의 위치를 n개 저장할 리스트
for i in range(n):
    a = list(map(int,input().split()))
    location.append(a)
# print(location)


def length(x,y,z,w):
    p = (x-z)**2 + (y - w) **2
    ans = math.sqrt(p)
    return ans


best_length = length(10000,10000,-10000,-10000)
min_d_l = 0
for i in range(n):
    max_d = 0
    max_d_l = 0
    for j in range(n):
        d = length(location[i][0],location[i][1],location[j][0],location[j][1])
        if max_d <  d:
            max_d = d
            max_d_l = i
    if max_d < best_length:
        best_length = max_d
        min_d_l = max_d_l

print(location[min_d_l][0],location[min_d_l][1])