백준 1026번 보물 [그리드 알고리즘]

백준 1026번 보물 [그리드 알고리즘]

두 수열 A,B가 주어졌고, 주어진 수식으로 프로그램을 구현했을 때, 최소 값이 나오도록 구현해야한다.

 

[제한 조건]

1. 배열 A는 재배열 할 수 있지만, B 배열은 재배열이 안된다.
2. 시간 제한 2초
3. 메모리 제한 128MB

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

 

 

[문제풀이과정]

1. 두 배열의 같은 위치에 있는 값들을 서로 곱하고, 모든 값들을 더 했을 때, 가장 작은 값이 나오도록 해야 한다.
2. 곱 연산에서 가장 작은 값을 구하려면 가장 작은 값과 가장 큰 값을 곱하면 된다.
3. 최초에 문제를 풀 당시에는 A 배열을 직접 한칸씩 옮기는 과정으로 진행하였다.
4. 하지만 해당 구현은 성능적으로도 안좋아서, 고민을 하다가,
   배열을 직접 옮기는 과정보다는 복사를 해서 사용하는게 좋을거 같았다.
5. 각 A 배열은 오름차순, B 배열은 내림차순으로 정렬해서, 최적의 위치에 맞게 구현하였다.

 

[코드]

counts = int(input())

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

b_orders = [B[i] for i in range(counts)]
b_orders.sort(reverse=True)

result = 0
for a,b in zip(A,b_orders):
    result += a*b
print(result)