파이썬 알고리즘 : 최솟값 만들기
2024년 1월 1일 알고리즘 문제풀이 문제 최솟값 만들기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 from heapq import heappop, heappush def solution(A,B): n = len(A) arr_A = [False for _ in range(n)] arr_B = [False for _ in range(n)] arr = [] def dfs(tmp,arr_A,arr_B): if arr and tmp > arr[0]: return if not arr_A.count(False) and not arr_B.count(False): if not arr or tmp < arr[0]: heappush(arr,tmp) for i in range(n): if arr_A[i]: continue for j in range(n): if arr_B[j]: continue arr_A[i] = True arr_B[j] = True dfs(tmp+(A[i]*B[j]),arr_A,arr_B) arr_A[i] = False arr_B[j] = False dfs(0,arr_A,arr_B) return arr[0] 처음엔 DFS로 시도했다. 여러 case가 규칙성 없이 나타날 수 있다고 생각했기 때문이다. 하지만 시간초과가 발생했다. 불필요한 탐색을 줄이기 위해, 값을 최소힙에 저장하도록 했다. DFS 과정 상 재귀 중에 이미 최소힙에 존재하는 최솟값을 넘어선 경우 탐색을 중단하도록 했다. 하지만 시간초과가 계속 발생했다. ...