블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 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
와 B
를 각각 오름차순과 내림차순 또는 내림차순과 오름차순으로 정렬의 순서를 바꾸어 정렬한 다음 각각의 요소를 for
반복문을 활용해 곱해서 더해주는 방법을 생각했다.
문제는 설명에 나와있는 B에 있는 수는 재배열하면 안 된다 는 문장이었다. 하지만 질문 페이지를 확인해보니 이 부분은 문제를 푸는 데 있어 무시해도 괜찮은 조건이라는 서술이 나와 있어 결국 무시하고 풀었다.
접근법을 토대로 아래와 같이 sorted()
내장함수를 활용해 하나의 배열은 오름차순으로, 다른 하나의 배열은 매개변수 reverse
의 값에 True
를 넘겨 내림차순으로 정렬하고 각각의 요소를 곱해주어 더해줬다.
N: int = int(input())
A: list[int] = list(map(int, input().split(" ")))
B: list[int] = list(map(int, input().split(" ")))
answer: int = 0
for A_num, B_num in zip(sorted(A), sorted(B, reverse=True)):
answer += (A_num * B_num)
print(answer)
아래와 같이 SUM()
함수 및 리스트 컴프리헨션을 사용하여 훨씬 짧게 문제를 풀이할 수도 있다.
N: int = int(input())
A: list[int] = list(map(int, input().split(" ")))
B: list[int] = list(map(int, input().split(" ")))
print(sum([ A_num * B_num for A_num, B_num in zip(sorted(A), sorted(B, reverse=True)) ]))
파이썬 내장 함수 sorted()
의 시간 복잡도가 O(NlogN)이기 때문에 for
반복문에서 배열의 길이 N
만큼, 다시 말해 O(N)의 시간 복잡도가 들더라도 정렬 때문에 결국 Big-O는 O(NlogN)이다.