[백준] 1026. 보물 (python)

 

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

import sys
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

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

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

print(result)

 

문제설명에서 b배열은 재배열하지 말고, a배열만 재배열하여

s의 최솟값을 구하라고 했는데 (s = a[0]*b[0] + ... + a[n-1]*b[n-1])

그렇다고 진짜 b배열은 가만히 두고 a배열만 b배열에 맞게 재배열하는 건 너무 먼 길 돌아가게 된다.

s의 최솟값을 구하려면 

a의 최솟값*b의 최댓값 + a의 두번재 최솟값*b의 두번째 최댓값 + ... 

이런식으로 계산해야 하기 때문에 a는 오름차순 정렬, b는 내림차순 정렬해서

순서대로 곱하고 더해준다.

그리디 유형이기 때문에 문제설명이 뭐라 하든 값을 찾을 수 있는 최선의 방법을 구해야 한다.

 

 

 

두번째 풀이

import sys
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

a.sort()

result = 0
for i in range(n):
    b_max = max(b)
    result += a[i]*b_max
    b.remove(b_max)

print(result)

 

혹시 몰라서 문제설명대로 b배열은 재배열하지 않고 풀어보았다.

a만 오름차순 정렬한 뒤 차례대로 원소를 빼주고, 

b원소에서는 최댓값을 찾아서 계산해준 뒤에 해당 값을 리스트에서 삭제한다.

이렇게 풀어도 정답은 나오는데 신기한게 첫번째 풀이보다 시간이 아주 약간 줄어들었다.

 

 

 

정렬 라이브러리인 sort()함수의 시간복잡도는 O(NlogN)

min, max 함수의 시간복잡도는 O(N)

리스트 삭제는 O(N)

 

시간 복잡도 계산은 아직 잘 할 줄 모르지만

첫번째 풀이 : O(2NlogN) + O(N)

두번째 풀이 : O(N*2N^2) = O(2N^2)

아닌감...? 해당 문제 테스트 예제의 값이 크지 않아서 시간 차이가 많이 나지 않는 걸까?

잘 모르겠다