백준 1026번 파이썬 풀이: 보물

백준 1026번 보물

 

알고리즘 분류: 정렬

 

링크: 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를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.

 

 

문제 파악

 

오랜만에 힌트가 있는 문제를 풀어보았다.

 

이 문제는 s의 최소값을 구하는 문제이므로 A배열에서 제일 작은 수와 B배열에서 제일 큰 수를

 

곱하고 그 다음으로 작은 수와 큰 수 이런식으로 계속해서 더해주면 되는 문제이다.

 

가장 간단하게 푸는방법은 A배열을 내림차순으로 정렬해주고 B배열을 오름차순으로 정렬해서

 

각각 인데스끼리 곱해서 더해주면 간단하게 풀 수 있지만

 

문제에서 B배열은 재배열하면 안된다고 명시되있기 때문에 다른 방법을 이용해서 풀어야한다.

 

그래서 A배열의 제일 작은 수와 B배열의 제일 큰 수를 곱해주고

 

이 제일 작은수와 제일 큰수는 pop을 이용해서 배열에서 빼주고 다시 반복하는 식의 로직을 만들었다.

 

 

코드

# 1026번

n = int(input())

a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

sorted_a = sorted(a_list, reverse=True)
sorted_b = sorted(b_list)

s = 0
for i in range(n):
    s += sorted_a[i] * sorted_b[i]

print(s)

앞서 말했듯이 A배열을 내림차순으로 정렬하고 B배열을 오름차순으로 정렬해서 각각 곱하고 더해주는 방식이다.

 

문제에 B배열은 재배열하면 안된다고 되어있지만 이렇게 풀어도 정답으로 인정은 된다.

 

그러나 문제를 제대로 풀기 위해서 이 방법말고 다른 방법으로도 풀어보았다.

 

# 1026번

n = int(input())

a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

s = 0
for i in range(n):
    s += min(a_list) * max(b_list)
    a_list.pop(a_list.index(min(a_list)))
    b_list.pop(b_list.index(max(b_list)))

print(s)

A배열의 최소값과 B배열의 최대값을 곱해서 s에 더해준다.

 

그리고 pop함수를 이용해서 A배열의 최소값과 B배열의 최대값을 배열에서 빼주는 걸 반복한다.

 

이 방식을 이용하면 B배열을 재배열하지 않아도 s의 최소값을 구할 수 있다.