57. Python 백준 1026 번 간단한 풀이, 정석 풀이

 

안녕하세요. 코딩하는 덕구입니다. Python 백준 1026 번 1로 만들기 입니다.

그리디 알고리즘 문제입니다.

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

1026번: 보물

 

 

예를들어 1, 4, 6, 9 라는 숫자가 주어졌을 때

이 숫자들을 두개씩 곱하고, 곱한 수들을 더해서 가장 작게 만들어야 될 때

우리는 직관적으로 가장 큰 수는 가장 작은 수와 곱해야 된다는 것을 알 수 있습니다.

1*9 = 9

4*9 = 36 

6*9 = 54

처럼 큰 수에 큰 수를 곱하면 값이 기하급수적으로 커지기 때문이죠.

 

백준 1026번 Python 간단한 풀이입니다.

A를 오름차순으로 정렬 (작은 수 부터 큰 수로)

B를 내림차순으로 정렬 (큰 수 부터 작은수로)

그리고 각 index에 맞춰서 곱 합니다.

가장 작은 수와, 가장 큰 수, 두 번째로 작은 수와, 두 번째로 큰 수....

i 번 째로 작은 수 와  i번 째로 큰 수가 곱해지면서 이 곱들의 합은 최소값이 되겠죠.

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
sum = 0
A.sort()
B.sort(reverse=True)

for i in range (N):
    sum += A[i] * B[i]
print(sum)

 

 

 

백준 1026번 Python 정석 코드입니다.

배열 B를 정렬하지 않는 조건을 만족하면서 문제를 풀어야 하므로

최대값과, 최소값을 뽑아서 곱하면 되겠죠.

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
sum = 0
for i in range (N):
    sum += A.pop(A.index(max(A))) * B.pop(B.index(min(B)))

print(sum)

사실 다양한 풀이가 있을 수 있습니다. 예를들어 B의 성분들의 크기 순으로 A의 성분들을 반대로 정렬하면 되겠죠

 

Python 백준 1026 번 이였습니다. 감사합니다.