백준 1026번: 보물 (Python)

https://www.acmicpc.net/problem/1026

1026번: 보물

---

Level: Silver IV

Solved By: Implementation

 

문제에서 등차수열이라 나오지는 않았었지만, A, B 둘 다 1부터 1씩 증가하는 등차수열이라 가정하고 풀이에 접근했습니다.

• A, B가 둘 다 증가하는 수열일 경우
• A는 증가하는 수열, B는 감소하는 수열일 경우

1번 경우에는 \( 1^2+2^2+...+n^2 \)로 풀이되어 이는 \( \sum_{k=1}^{n}k^2 \)로 거듭제곱 수의 합 공식에 의해 아래와 같습니다.

$$ \frac{n(n+1)(2n+1)}{6} = \frac{2n^3+3n^2+n}{6} $$

2번 경우에는 \( 1\times n+2\times(n-1)+...+(\frac{n}{2})^2+...+(n-1)\times2+n\times1 \)로 풀이되고, \(2\lbrace\sum_{k=1}^{n}k(n-k)\rbrace+\frac{n^2}{2}\)로 정리되어 아래와 같이 나타날 수 있습니다.

$$ \frac{n^3-n^2-n}{3} $$

즉, 2번의 경우가 최솟값을 구하는 답이 되기 때문에 A는 오름차순으로 정렬, B는 내림차순으로 정렬하여 반복문을 통해 원소들을 서로 곱해준 값들을 모두 더하여 출력하면 풀 수 있는 문제였습니다.

 

+ 문제를 풀고나서 든 생각인데 \(A = \lbrace1, 2, 3\rbrace, B = \lbrace3, 2, 1\rbrace\)로 간단하게 가정을 했다면 더 빨리 쉽게 풀지 않았을까 싶습니다 :)

n = int(input())

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

A.sort()
B.sort(reverse=True)

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

print(answer)