[백준/BOJ] 백준 코딩 알고리즘 1026번/Python

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

코드

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort()

answer_list = ['0' for i in range(N)]
copy_b = B.copy()

for i in range(0, N):
  a_min_idx = A.index(min(A))
  b_max_idx = copy_b.index(max(copy_b))
  
  answer_list[b_max_idx] = A[a_min_idx]

  A[a_min_idx] = 101
  copy_b[b_max_idx] = -1

answer = 0
for i in range(0, N):
  answer += answer_list[i] * B[i]

print(answer)

설명

• 문제이름 및 번호: 보물(1026번)
• 시간복잡도: O(N)
• 관련 알고리즘: 그리디 알고리즘

 

• B 배열의 순서는 그대로 두고, A배열만 순서를 바꾸어 각 인덱스끼리 곱하여 합했을 때 최소값을 구해야 한다
• 이를 위해서는 B 배열에 있는 최대값들을 가장 많이 줄이기 위해 A 배열의 최소값 순서대로 곱해주면 된다
• 따라서 B 배열의 최대값 목록을 A 배열의 최소값 순서에 따라 곱해주었다

 

• 그리디 알고리즘에 따라 직관적으로 떠오른 아이디어는 좋았던 것 같으나, N 길이의 for문을 2번 돌았던 점이 아쉽다
• 또한 입력 리스트와 동일한 길이의 리스트를 2개나 더 생성해서, 메모리 측면에서 낭비가 좀 있었던 것 같다
• 이를 최소화할 수 있도록 고민해보면 좋을 것 같다