[BOJ/BaekJoon] 백준 1026 보물 (Python / 파이썬)

BaekJoon BOJ 백준 1026 보물 문제는 길이가 N인 정수 배열 2개 중 1개를 재배열하여 함수의 최솟값을 구하는 문제이다.

 

BaekJoon 1026 보물 문제 정보

출처

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

알고리즘 분류

- 그리디 알고리즘 (greedy algorithm, 탐욕법)

난이도

- 실버 4 / Silver 4

 

보물 문제 요약

• 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의한다.
  • S = A [0] × B [0] +... + A [N-1] × B [N-1]
• S의 값을 가장 작게 만들기 위해 A의 수를 재배열한다.
• 단, B에 있는 수는 재배열하면 안 된다.
• 첫째 줄에 N이 주어진다. (N은 50보다 작거나 같은 자연수)
• 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어진다.
• 셋째 줄에는 B에 있는 수가 순서대로 주어진다 (A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수)
• S의 최솟값을 구하여 출력한다.
  

문제 풀이 과정

곱의 합이 최소가 되려면 A의 큰 수 * B의 작은 수 끼리 더하면 된다.
따라서 하나는 오름차순, 하나는 내림차순으로 정렬 후 계산하면 된다.

 

1. 정수 배열의 길이 N, 정수 배열 A, B를 입력받는다.
2. A 배열을 내림차순, B 배열을 오름차순으로 정렬한다.
3. 배열의 각 원소들을 곱한 뒤 그 결과를 더한다.
4. 결과를 출력한다.

 

코드 및 설명

• N - 정수 배열의 길이
• A, B - 정수 배열
• result - S의 최솟값

N = int(input())

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

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

result = 0

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

print(result)

---

 

BaekJoon 백준 BOJ 1026 보물 문제를 파이썬 python으로 풀어보았다. 난이도는 Silver 실버 4이다.