[백준] 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의 최솟값을 출력한다.

​

입출력 예

input	output
5 1 1 1 6 0 2 7 8 3 1	18

접근법

이번 방법은 두 가지로 풀 수 있을 것 같습니다. 먼저 문제를 풀기 위해서는 b의 가장 큰값과 a의 가장 작은 값을 곱해주고, b의 두번째로 큰 값과 a의 두번째로 작은 값을 곱해주고, .. 하는 방식으로 계속 이어나가면 됩니다.

첫 번째는 문제에서 주어진 것 처럼 b리스트를 건들지 않고, a만을 이동하여 푸는 방법입니다. 먼저 b 리스트 내의 값을 내림차순 으로 정렬 했을 때, 그 인덱스 값을 가지는 리스트를 생성해 줍니다.

예를 들어 [2, 7, 8, 3, 1]값을 내림차순으로 정렬하면 [8, 7, 3, 2, 1]이죠. 이 리스트 내의 값이 b리스트에서 어떤 인덱스에 존재하는지 찾아서 리스트를 생성해 주시면 됩니다. 8은 b리스트 내에서 인덱스 2에 존재하기 때문에 2, 7은 1, 3은 3, 2는 0, 1은 4,.. 이런식으로 [2, 1, 3, 0, 4]라는 리스트가 생성됩니다. a리스트는 오름차순으로 정렬해준 뒤, 반복 문을 돌면서,a 리스트[i]와 b리스트[인덱스 리스트[i]]를 곱해주시면 됩니다.

두 번째 방법은 b리스트는 내림차순, a리스트는 오름차순으로 정렬하여 문제를 푸는 방법입니다. 문제에서는 조건으로 b를 정렬시키지 말라고 하였는데, 이렇게 제출해도 성공하더라구요!

​

나의 코드

(1) 첫 번째 방법

import sys

number = int(input())

a_list = list(map(int, sys.stdin.readline().split()))
b_list = list(map(int, sys.stdin.readline().split()))

index_list = [0] * number
for i, item in enumerate(sorted(b_list, reverse=True)):
    index_list[i] = b_list.index(item)

a_list.sort()
sum = 0
for i in range(number):
    sum += a_list[i]*b_list[index_list[i]]
print(sum)

​

​(2) 두 번째 방법

import sys

number = int(input())

a_list = list(map(int, sys.stdin.readline().split()))
b_list = list(map(int, sys.stdin.readline().split()))

a_list.sort()
b_list.sort(reverse=True)
sum = 0
for i range(number):
    sum += a_list[i]*b_list[i]
print(sum)