[백준 알고리즘] 1026번 : 보물 (Python) 문제 풀이

문제

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

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

 

https://www.acmicpc.net/problem/1026

1026번: 보물

 

문제 풀이 :  이 문제는 그리디 알고리즘을 이용하는 문제이다.

문제를 읽어보면

"S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다."

S의 값을 가장 작게 만들기위한 욕심 즉, 최적해값을 구하는 것이다.

 

여기서 조건은 

1. A는 재배열 해도된다.

2. B는 재배열 해서는 안된다.

이다. 

 

S의 값을 가장 적게 만들기위해서는 A의 가장 작은 값부터 B의 가장 큰 값과 곱을 해주면 된다.

그렇다면 A를 작은 순부터 정렬하고 B의 가장 큰 값부터 뽑아서

곱해준 다음 그 값을 sum이라는 변수에 다 더해주면 된다. 

간단하다.

 

내 코드 : 

num = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
temp_B = B
A =sorted(A)
 
sum = 0
for i in range(num) : 
    sum += (A[i] * temp_B[temp_B.index(max(temp_B))])
    temp_B.remove(max(temp_B))
 
print(sum)