백준 1026번 바로가기

첫 번째 풀이

KMO 같은 수학 경시대회를 풀어본 경험이 있다면, 직관적으로 이 문제를 보자마자 A배열을 오름차순, B배열을 내림차순해서 각 원소를 곱해주면 되겠다는 발상을 떠올릴 것이다. 다음과 같은 코드로 쉽게 문제를 해결할 수 있다.

import sys

n = int(sys.stdin.readline())
arr_1 = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
arr_2 = sorted(list(map(int, sys.stdin.readline().split())), reverse=False)

ans = 0
for i in range(n):
    ans += arr_1[i] * arr_2[i]
    
print(ans)

두 번째 풀이

다만, 이 문제의 경우 단, B에 있는 수는 재배열하면 안 된다. 라는 제한조건이 걸려있기 때문에 바람직한 풀이는 아니다. 위처럼 A, B배열 모두 정렬해서 제출하더라도 정답처리는 되지만, 출제 의도에 맞게 다시 풀어보자. A배열을 정렬한 상태에서 B에서 최솟값을 하나씩 뽑아내는 방법이다. 결국엔 같은 방법같긴 하지만, 문제의 취지에 맞게 greedy로 풀었다.

import sys

n = int(sys.stdin.readline())
arr_1 = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
arr_2 = list(map(int, sys.stdin.readline().split()))

ans = 0
for i in range(n):
    temp = min(arr_2)
    ans += arr_1[i] * temp
    arr_2.remove(temp)
    
print(ans)

번외 풀이

사실 arr_1에서 max값, arr_2에서 min값을 하나씩 뽑아서 서로 곱해주는 방법도 있긴 하다. 하지만 코드가 길어지고 너저분해지기 때문에 별로인 것 같다.

import sys

n = int(sys.stdin.readline())
arr_1 = list(map(int, sys.stdin.readline().split()))
arr_2 = list(map(int, sys.stdin.readline().split()))

ans = 0
for _ in range(n):
    temp1 = max(arr_1)
    temp2 = min(arr_2)
    ans += temp1 * temp2
    arr_1.remove(temp1)
    arr_2.remove(temp2)
    
print(ans)