완전탐색 1090번 시간초과

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

완전탐색 (For반복문)

작성

471

예제 문제는 잘 풀리는데 백준에 제출하니까 시간초과가 뜹니다

강의 자료랑 큰 차이는 없어 보이는데 어느 부분을 고쳐야 시간 안에 계산 가능할까요?

#include <iostream>
#include <cstdlib>
using namespace std;

int main(int argc, char **argv) {
	int n;
  int minX, minY, maxX, maxY; 
  cin >> n;
  
  int arr[n][2];
  
  for(int i=0; i<n; i++){
    cin >> arr[i][0] >> arr[i][1];
  }

  minX = arr[0][0]; maxX = arr[0][0]; 
  minY = arr[0][1]; maxY = arr[0][1];
  for(int i=1; i<n; i++){  
    if(arr[i][0]>maxX){
      maxX = arr[i][0];
    }
    else if(arr[i][0]<minX){
      minX = arr[i][0];
    }
    if(arr[i][1]>maxY){
      maxY = arr[i][1];
    }
    else if(arr[i][1]<minY){
      minY = arr[i][1];
    }
  }  
  int arr_answer[n];
  int arr_dis[n];
  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);
      }
      
      int sum = 0;
      for(int k=0; k<n; k++){
        sum+=arr_dis[k];
        if(i==minY && j ==minX){
          arr_answer[k] =sum;
        }
        else if(sum < arr_answer[k]){
          arr_answer[k] = sum;
        }
      }

    }
  }

  for(int i=0; i<n; i++){
    cout << arr_answer[i] << " ";
  }

  return 0;
}

python 코딩-테스트 알고리즘

답변 2

규진

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

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

코딩 센세

지식공유자

보여주신 코드에서 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);
      }

인프런 커뮤니티 질문&답변

완전탐색 1090번 시간초과