[파이썬 | BOJ | 1026] 보물

https://www.acmicpc.net/problem/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 리스트의 내림차순 순위를 나타내는 ARank, BRank 리스트를 만들어서, ARank가 가장 작은값과 BRank가 가장 큰 값을 매칭시킨다.

 

내가 더 좋은 알고리즘을 못찾은 것일수도 있는데, A, B 리스트에 같은 값이 들어오게되면, 일반적인 Rank를 구하는 알고리즘은 같은 값을 가지면 같은 Rank를 구하게 된다.

하지만 이번에는 같은 값이라도, 다른 Rank를 부여하게 억지로 코드를 짜다보니까 상당히 복잡해졌다.

 

import sys
read = sys.stdin.readline

N = int(read())
A = list(map(int, read().split()))
B = list(map(int, read().split()))

ARank = [0 for _ in range(len(B))]
BRank = [0 for _ in range(len(B))]

for i in range(len(B)):
    BRank[i] += 1
    for j in range(len(B)):                 #B[i]보다 큰 값들의 개수를 찾는다.
        if B[i] < B[j]:
            BRank[i] += 1
    while BRank.count(BRank[i]) > 1:        #B[i]가 이미 BRank 리스트에 존재하면, 값을 증가시켜서 중복 순위를 피한다
        BRank[i] += 1
        
    ARank[i] += 1
    for j in range(len(A)):
        if A[i] < A[j]:
            ARank[i] += 1
    while ARank.count(ARank[i]) > 1:
        ARank[i] += 1

ans = 0

for i in range(N):
    jval = N+1-ARank[i]
    j = BRank.index(jval)
    ans += A[i] * B[j]
print(ans)

 

문제를 풀고나서 생각해보니, 그냥 A리스트에서 제일 큰 값과 B리스트에서 제일 작은 값을 매칭시킨 후, 그 값들을 pop하면서 반복하면 매우 간단하게 풀이가 가능했다.

 

import sys
read = sys.stdin.readline

N = int(read())
A = list(map(int, read().split()))
B = list(map(int, read().split()))

ans = 0

while len(A):
    ans += max(A) * min(B)
    A.pop(A.index(max(A)))
    B.pop(B.index(min(B)))
    
print(ans)