[백준][1026] - 보물 python 파이썬

보물 - 1026

1026번: 보물

분류

그리디 알고리즘, 수학, 정렬

문제 설명

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

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

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

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

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

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

---

🙋 문제 해석

먼저 이문제는 A배열의 가장 작은수와 B배열의 가장 큰수를 이용해서 문제를 풀 수 있다. 두 배열 모두 정렬을 사용하면 쉽게 풀수 있지만 제약조건이 있기 때문에 가능한 지키면서 풀어보았다.

---

🚫 TRY 01

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

s = 0
for i in range(n):
    s += a[i] * b[i]

print(s)

먼저 a,b모두 정렬을 사용해서 풀 때는 다음과 같다.

---

🔑 Solution 🔑

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
s = 0
for i in range(n):
    b_max = max(b)
    s += a[i] * b_max
    b.remove(b_max)

print(s)

위 코드는 B 리스트만 정렬을 안하고 푼 문제이다. 가장 큰 숫자를 pop을 해서 n번째로 큰 수를 찾으면 된다.

 

A를 오름차순으로 정렬

1. B에서 가장 큰 수와 A에서 가장 작은 수를 곱한 값을 S에 더하기

2. max(b) pop하기

3. B에서 가장 큰 수와 A에서 n 번째로 큰 수를 곱한 값을 S에 더하기

1,2,3 과정 반복

위와 같은 방법으로 A만 정렬하고 B는 정렬하지 않고도 S의 최솟값을 구할 수 있다.

 

이때 그리디 알고리즘의 탐욕 선택 속성은 "B에서 가장 큰 수와 A에서 작은 수를 곱한 값이 S를 가장 작게 만드는 최선의 선택이다"라고 말할 수 있다.

그리디(Greedy) 알고리즘 예시와 문제

---

🕐 시간 복잡도

• 함수 max와 pop 함수를 사용하고 있기 때문에, 이 알고리즘의 시간 복잡도는 O(n^2)이 된다.

---

🙇