[Baekjoon] 1026번 보물

보물

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	37998	24008	20428	65.740%

문제

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

길이가 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의 최솟값을 출력한다.

예제 입력 1 복사

5
1 1 1 6 0
2 7 8 3 1

예제 출력 1

18

문제 풀이

• 배열 하나는 asending 으로 하면 되고 나머지 하나는 descending order로 해야 하기 때문에 이 때 부호를 마이너스로 바꾸어 sorting을 진행하면 해결된다.
• sorting 알고리즘 중에서 버블 정렬을 사용하여 풀었다.

def bubble_sort(unordered):
    iteration = len(unordered) - 1
    for i in range(iteration):
        for j in range(iteration - i):
            if unordered[j] > unordered[j+1]:
                unordered[j], unordered[j+1] = unordered[j+1], unordered[j]


n = int(input())

_a = list(map(int, input().split()))
_b = list(map(int, input().split()))
minus_b = list(map(lambda x: -x, _b))

bubble_sort(_a)
bubble_sort(minus_b)

_b = list(map(abs, minus_b))

print(sum(_a[i] * _b[i] for i in range(len(_a))))

• 다음 코드는 정렬 알고리즘을 익히기 위해서 퀵 정렬로도 풀어본 결과이다.

import sys


def partition(unsorted, first, last):
    pivot = unsorted[first]
    left = first + 1
    right = last

    while True:
        while unsorted[left] <= pivot and left < last:
            left += 1
        while unsorted[right] > pivot and right >= first:
            right -= 1

        if left < right:
            unsorted[left], unsorted[right] = unsorted[right], unsorted[left]
        else:
            break

    unsorted[first], unsorted[right] = unsorted[right], unsorted[first]
    return right  # pivot index


def quick_sort(unsorted, first, last):
    if first < last:
        pivot_index = partition(unsorted, first, last)
        quick_sort(unsorted, first, pivot_index-1)
        quick_sort(unsorted, pivot_index+1, last)



n = int(input())
_a = list(map(int, input().split()))
_b = list(map(int, input().split()))

minus_b = list(map(lambda x: -x, _b))

quick_sort(_a, 0, len(_a) - 1)
quick_sort(minus_b, 0, len(minus_b)-1)

_b = list(map(abs, minus_b))

print(sum(_a[i] * _b[i] for i in range(len(_a))))

일반적으로 퀵 정렬이 좋은 성능을 보인다고 알려져 있지만 쉬운 문제에서는 단순한 버블 정렬로도 쉽게 풀 수 있으며 시간 또한 버블 정렬이 더 빠른 것을 알 수 있었다.