[프로그래머스] 최솟값 만들기

 


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