投稿した質問数 2

0

다른 질문글에서는 2차원일 때 집 뿐만아니라 minx, miny 사이 값을 탐색해야한다고 하셨던 것 같은데 (첫 입력예시에 의하면 9개 경우의수) 제가 이해한게 맞을까요?

저도 시간초과 나와서 질문 남깁니다

0

보여주신 코드에서 X Y좌표의 min값과 max값을 계산해서 배열에 담고, 그 사이 범위를 모두 확인하도록 계산했지만 수업에서 설명한것처럼 각각의 집이 있는 좌표만 확인해주면 됩니다.

제가 작성한 코드는 아래와 같이 처음에 입력을 받은 좌표를 이용해서 바로 계산을 하지만,

n = int(input())
arr = []
arr_y = []
arr_x = []
answer = [-1]*n

# 입력 받기
for _ in range(n):
    a,b = map(int,input().split())
    arr.append([a,b])
    arr_y.append(b)
    arr_x.append(a)

# 만날 장소 정하기
for y in arr_y:
    for x in arr_x:
        dist = []
        
        # 만날 장소로 각각의 점들이 오는 비용 계산하기
        for ex,ey in arr:
            d = abs(ex-x) + abs(ey-y)
            dist.append(d)

        
        # 가까운 순서대로 정렬하기
        dist.sort()

        tmp = 0 
        for i in range(len(dist)):
            d = dist[i]
            tmp += d
            if answer[i] == -1: 
                answer[i] = tmp
            else :
                answer[i] = min(tmp, answer[i])

print(*answer)

보내주신 코드는 최댓값 최솟값을 계산하고, 그 안의 숫자를 모두 반복문으로 확인해서 정답을 계산하고 있습니다.

예제

[1_000_000, 0] 좌표의 집과 [0,1_000_000] 좌표의 집이 있다면

저의 코드

[1_000_000, 0]

[1_000_000, 1_000_000]

[0,1_000_000]

[0,0]

4개의 지점을 확인하고 반복문이 종료됩니다.

# 만날 장소 정하기
for y in arr_y:
    for x in arr_x:
        dist = []
        
        # 만날 장소로 각각의 점들이 오는 비용 계산하기
        for ex,ey in arr:
            d = abs(ex-x) + abs(ey-y)
            dist.append(d)

질문 주신 코드

[0,0], [0,1], [0,2], [0,3], ... , [ 1_000_000 , 1_000_000 ]

100만 * 100만개의 지점을 확인 한 뒤에 반복문이 종료됩니다.

 for(int i=minY; i<=maxY; i++){
    for(int j=minX; j<= maxX; j++){
      for(int l=0; l<n; l++){    
        int subY= 0, subX=0;
        subY = i-arr[l][1];
        subX = j-arr[l][0];
        arr_dis[l] = abs(subX) + abs(subY);
      }