오늘 문제는 보물! 그리디 알고리즘 유형의 문제입니다. 살펴보겠습니다!!
1. 오늘의 학습 키워드
- 그리디 알고리즘
2. 문제: 보물 (1026번)
- 단계: 🥈 실버4단계
- 유형: 수학, 그리디 알고리즘, 정렬
- 출처: https://www.acmicpc.net/problem/1026
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 65639 | 44454 | 37837 | 69.690% |
문제
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 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의 최솟값을 출력한다.
예제 입력 1 복사
5
1 1 1 6 0
2 7 8 3 1
예제 출력 1 복사
18
예제 입력 2 복사
3
1 1 3
10 30 20
예제 출력 2 복사
80
예제 입력 3 복사
9
5 15 100 31 39 0 0 3 26
11 12 13 2 3 4 5 9 1
예제 출력 3 복사
528
힌트
예제 1의 경우 A를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.
출처
- 문제를 번역한 사람: baekjoon
알고리즘 분류
3. 나의 풀이
문제 이해 및 접근
이 문제는 두 배열 A와 B를 사용하여 주어진 조건에 맞게 곱셈의 합을 최소로 만드는 문제입니다. 배열 A는 재배열할 수 있지만, 배열 B는 재배열할 수 없습니다. 주어진 수식 S를 최소로 만들기 위해서는 가장 큰 값과 가장 작은 값을 곱하는 방식으로 최적해를 구할 수 있습니다. 이 문제는 그리디 알고리즘을 사용하여 해결할 수 있습니다.
그리디 접근 방법
- 배열 A의 가장 작은 값과 배열 B의 가장 큰 값을 곱합니다.
- A와 B에서 각각 이 값들을 제거한 후, 다시 반복합니다.
- 이 과정을 반복하면서 전체 곱셈 합을 최소화합니다.
코드 설명
import sys
def sol(N, A, B):
result = 0
# A와 B에서 각각 최소, 최대값을 찾아 곱셈하고 배열에서 제거
for i in range(N):
result += min(A) * max(B) # A의 최소값과 B의 최대값을 곱해서 더함
A.pop(A.index(min(A))) # A에서 최소값 제거
B.pop(B.index(max(B))) # B에서 최대값 제거
return result # 최종 결과 반환
# 입력 처리
N = int(sys.stdin.readline().strip()) # 배열의 길이 N
A = list(map(int, sys.stdin.readline().split())) # 배열 A
B = list(map(int, sys.stdin.readline().split())) # 배열 B
# 결과 출력
print(sol(N, A, B))
풀이 과정
- 입력 처리: 배열 A와 B는 입력을 받아 각각 리스트로 저장됩니다.
- 최소값과 최대값 계산: 매번 배열 A에서 최소값을, 배열 B에서 최대값을 찾아 그 값들을 곱합니다.
- 반복: A와 B에서 각각 해당 값들을 제거한 후, 이 과정을 N번 반복합니다.
- 결과 반환: 각 곱셈의 합을
result에 저장하고 최종적으로 반환합니다.
시간 복잡도
- 매번
min(A)와max(B)를 찾아야 하므로 의 시간 복잡도를 가집니다. 이 방식은pop과index를 매번 사용하는 방식이기 때문에 시간 복잡도가 높습니다.
더 효율적인 개선 방법
위의 코드는 min과 max를 반복해서 사용하면서 매번 리스트를 탐색하기 때문에 의 시간 복잡도를 가집니다. 이를 더 효율적으로 개선할 수 있습니다.
개선된 코드
import sys
def sol(N, A, B):
A.sort() # A는 오름차순으로 정렬
B.sort(reverse=True) # B는 내림차순으로 정렬
result = 0
for i in range(N):
result += A[i] * B[i] # 각각의 요소를 곱하여 결과에 더함
return result
# 입력 처리
N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
# 결과 출력
print(sol(N, A, B))
개선된 풀이 과정
- 정렬: 배열 A는 오름차순으로 정렬하고, 배열 B는 내림차순으로 정렬합니다. 이렇게 하면 A의 가장 작은 값이 B의 가장 큰 값과 곱해집니다.
- 곱셈과 합산: 정렬된 배열 A와 B의 값을 차례대로 곱해서 합을 구합니다.
개선된 시간 복잡도
- 정렬은 의 시간 복잡도를 가지므로, 전체 시간 복잡도는 으로 매우 효율적입니다.
하지만 N이 50이하의 자연수이므로 이전 방법도 크게 문제는 없습니다!
마무리
이번 문제는 그리디 알고리즘과 정렬을 활용한 문제로, 배열 A와 B에서 각각 적절한 값을 선택하여 최소한의 곱셈 결과를 도출하는 방식으로 풀 수 있었습니다. 처음에는 min과 max를 반복해서 구하는 방식으로 풀이했지만, 이를 정렬로 개선하여 의 시간 복잡도를 가짐으로써 성능을 크게 향상시켰습니다.
그리디 알고리즘에서 최소 또는 최대를 선택하는 문제는 정렬을 사용하여 쉽게 해결할 수 있음을 다시 한 번 확인할 수 있었습니다.
Keep going!!!
