[백준 1026번] 보물

문제 링크 >> https://www.acmicpc.net/problem/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의 최솟값을 출력한다.

 

 

📝 풀이

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

answer = 0
for _ in range(n):
  answer += min(A) * max(B)
  A.remove(min(A))
  B.remove(max(B))
  
print(answer)

 

문제를 다 읽기 전에 생각한 풀이 방법은 A는 오름차순으로, B는 내림차순으로 정렬한 뒤 같은 인덱스의 요소끼리 곱하는 것이었다.

근데 B는 재배열하면 안 된다는 조건이 붙어 이 부분을 생각하는 게 좀 까다로웠다.

 

그 다음으로 생각한 풀이는 B를 정렬하지 않되 튜플형으로 바꾸어 크기 순으로 번호를 매기는 것이었다.

이 방법을 시도하다 조금 번거롭게 느껴져 다른 풀이를 생각할 수밖에 없었다.

 

결국 제출한 풀이 방법은 A와 B를 살펴보며 A에서는 최솟값을, B에서는 최대값을 뽑는다.

이 방법이 B를 재배열하지 않는지는 잘 모르겠지만 B를 정렬하지는 않고 있으니 이 풀이 방법이 맞지 않을까 싶다.