1. 문제
https://programmers.co.kr/learn/courses/30/lessons/12941
2. 풀이
2.1. dfs 를 사용한 시간 초과 풀이
- 특별한 방법이 떠오르지 않아서 dfs를 사용한 완전탐색을 이용하였으나 시간 초과되었습니다.
- 트리의 높이가 1000 라서 시간을 극복할 수 없습니다.
answer = 98765432100
N = 0
def dfs(depth, A, B, value):
global is_visited, answer
if value >= answer:
return
if depth == N:
answer = min(answer, value)
return
for i in range(N):
if is_visited[i] == 0:
is_visited[i] = 1
dfs(depth + 1, A, B, value + A[depth] * B[i])
is_visited[i] = 0
return
def solution(A, B):
global N, is_visited, answer
N = len(A)
is_visited = [0] * len(A)
dfs(0, A, B, 0)
return answer
2.2. 배열 정렬을 이용한 풀이
- 배열 하나는 내림차순, 하나는 오름차순으로 정렬하여 각 index 별로 곱해주면 값을 구할 수 있습니다.
def solution(A,B):
answer = 0
A = sorted(A)
B = sorted(B, reverse=True)
answer = sum([a * b for a, b in zip(A, B)])
return answer
PREVIOUS[프로그래머스] 다리를 지나는 트럭 풀이