[백준] 1026번 : 보물 (🥈실버 4) (Python)

문제 바로 가기

1026번: 보물

 

---

풀이 1

• 사용 언어 : Python
• 풀이한 날짜 : 2022-03-05

n = int(input())

lst_a = list(map(int, input().split()))
lst_b = list(map(int, input().split()))

lst_a.sort()
lst_b.sort(reverse=True)

ans = 0
for elem1, elem2 in zip(lst_a, lst_b):
    ans += elem1 * elem2

print(ans)

 

풀이 로직

• S의 값을 최소로 만들려면, 한 배열의 최댓값을 다른 배열의 최솟값과 곱하여, 값이 크게 불어나지 않도록 해야 한다.
• 따라서, A의 최댓값을 B의 최솟값과 곱하고, B의 최댓값의 A의 최솟값과 곱하면 S의 값을 최소로 할 수 있다.
• A, B의 남은 수들에도 이와 같은 과정을 재귀적으로 반복한다. 그럼 S의 최솟값 계산식을 아래처럼 정리할 수 있다.
  • (최댓값) _ (최솟값) + (2번째로 큰 값) _ (2번째로 작은 값) + ... + (최솟값) * (최댓값)

 

• 이를 코드로 구현해보자. 우선, A와 B를 서로 반대 방향으로 각각 정렬하고, 두 배열의 같은 index 원소끼리 서로 곱한 값을 모두 더해서 답을 계산한다.

 

문제 접근 과정 및 느낀점

• 처음 문제로 보고 머릿 속에 떠오른 풀이는 2가지였다.
  • 완전 탐색으로 모든 경우를 확인하기
  • (최댓값) * (최솟값) + (2번째로 큰 값) * (2번째로 작은 값) + ... + (최솟값) * (최댓값)
• 이 때, 완전 탐색으로 푸는 방법은 시간복잡도가 O(n!)인 매우 비효율적인 풀이라는 것을 확인하고 두 번째 방법을 선택하였다.

 

• 풀이를 마치고 다른 풀이를 알아보기 위해 구글에 서칭한 결과 대부분 내가 풀이한 방식과 동일하였다.
• 다만, B에 있는 수는 재배열 하면 안된다는 조건 때문에, A 배열만 재배열해서 푸신 분도 꽤 있었다.
• 그 중 어떤 분은, B배열도 재배열한 풀이는 잘못된 풀이라고 지적하셨는데, 나는 그렇진 않다고 생각한다.
• 왜냐하면, B를 재배열해선 안된다는 조건은 어디까지나 문제 상황을 설명하기 위한 조건일 뿐, 결국 S의 최솟값을 구하는 것이 문제의 최종 요구사항이기 때문이다.
• 하지만, 학습을 위해 B의 배열을 그대로 두고 계산하는 풀이도 직접 구현해서 어래에 남겼다.

풀이 2

• 사용 언어 : Python
• 풀이한 날짜 : 2022-03-05

n = int(input())

lst_a = list(map(int, input().split()))
lst_b = list(map(int, input().split()))

lst_a.sort()

ans = 0
for elem in lst_a:
    max_in_b = max(lst_b)
    lst_b.pop(lst_b.index(max_in_b))

    ans += elem * max_in_b

print(ans)

 

풀이 로직

• 로직은 위 풀이와 동일하다.
• 다만, 이번엔 B를 재배열하지 않고, max, index, pop 함수를 사용하여 배열 B의 최댓값을 불러오고 삭제하는 방식으로 S의 최솟값을 계산하였다.