백준 1026번 보물 Python 풀이

🔷 백준 1026번 보물 Python 풀이

🔷 문제 설명

문제

길이가 \(N\)인 두 개의 정수 배열 \(A\), \(B\)가 있습니다. 아래와 같이 \(S\)라는 값을 정의합니다.

\[ S = A[0] \times B[0] + A[1] \times B[1] + \cdots + A[N-1] \times B[N-1] \]

이때, 배열 \(A\)의 원소들을 재배열하여 \(S\)의 값을 최소화해야 합니다. 배열 \(B\)는 재배열할 수 없습니다.

입력

• 첫째 줄: 배열의 길이 \(N\) (\(1 \leq N \leq 50\))
• 둘째 줄: 배열 \(A\)의 \(N\)개의 원소 (각각 \(0 \leq A[i] \leq 100\))
• 셋째 줄: 배열 \(B\)의 \(N\)개의 원소 (각각 \(0 \leq B[i] \leq 100\))

출력

• \(S\)의 최소값을 출력합니다.

🔷 테스트케이스

입력 예시 1

5
1 1 1 6 0
2 7 8 3 1

출력 예시 1

18

입력 예시 2

3
1 1 3
10 30 20

출력 예시 2

80

입력 예시 3

9
5 15 100 31 39 0 0 3 26
11 12 13 2 3 4 5 9 1

출력 예시 3

528

🔷 문제설명

만약 \(A\)와 \(B\)를 그대로 곱하면 최소가 되지 않는 경우가 생깁니다. 예를 들어 \(A = [3, 1]\), \(B = [100, 1]\)이면 그대로 곱하면 \(3×100 + 1×1 = 301\)인데 \(A\)를 재배열하여 \(A = [1, 3]\)로 하면 \(1×100 + 3×1 = 103\)로 훨씬 작아집니다. 즉, 큰 수에 작은 수를 곱하고, 작은 수에 큰 수를 곱하는 방식으로 최소를 만들어야 합니다.

🔷 아이디어

• 배열 \(B\)는 고정이므로 \(B\)에서 큰 수는 가급적 작은 수와 곱해야 합니다.
• 따라서:
  • 배열 \(A\)는 오름차순(작은 순서)으로 정렬합니다.
  • 배열 \(B\)는 내림차순(큰 순서)으로 정렬한 복사본을 임시로 사용합니다.
  • 두 배열의 같은 인덱스끼리 곱하여 모두 더하면 최소의 \(S\)를 얻습니다.

🔷 전체 코드 Python

N = int(input())

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

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

sum_1 = 0
for i in range(N):
    sum_1 += A[i] * B[i]

print(sum_1)

🔷 개별 코드 설명

입력 처리

N = int(input())

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

배열 길이 \(N\)을 입력받고, \(A\)와 \(B\)의 값들을 차례로 입력받습니다.

정렬

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

\(A\)는 작은 값부터 차례로 나오도록 오름차순 정렬합니다. \(B\)는 큰 값부터 나오도록 내림차순 정렬한 복사본을 사용합니다. 이렇게 하면 작은 값과 큰 값이 곱해지도록 하여 \(S\)를 최소로 합니다.

합산

sum_1 = 0
for i in range(N):
    sum_1 += A[i] * B[i]

정렬된 \(A\)와 \(B\)의 같은 인덱스끼리 곱해 모두 더하면 최소의 \(S\)가 됩니다.

출력

print(sum_1)

최종 \(S\)의 최소값을 출력합니다.

🔷 결론

• \(A\)와 \(B\)는 각각 오름차순, 내림차순으로 정렬하여 곱해야 최소의 합이 나옵니다.
• \(B\)는 고정이므로 \(A\)만 재배열하는 것이 핵심입니다.
• 정렬 후 같은 인덱스끼리 곱하면 됩니다.
• 시간 복잡도는 \(O(N\log N)\)로 \(N \leq 50\)이므로 충분히 빠릅니다.

✅ 배열 \(A\)는 작은 수부터, 배열 \(B\)는 큰 수부터 배치
✅ 같은 위치끼리 곱해 합산
✅ \(B\)는 재배열 불가, \(A\)만 정렬 가능
✅ 정렬만 하면 로직은 간단합니다.