[그리디] 코딩테스트 문제 TIL (보물) - 백준 1026번

오늘 문제도 그리디 알고리즘 유형의 문제입니다.

---

1. 오늘의 학습 키워드

• 그리디 알고리즘
• 정렬

---

2. 문제: 1026. 보물

• 단계: 🥈실버 4단계
• 알고리즘 분류:
  • 수학
  • 그리디 알고리즘
  • 정렬
• 출처: https://www.acmicpc.net/problem/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의 최솟값을 출력한다.

예제 입력 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}과 같이 재배열하면 된다.

---

3. 문제 풀이

Step1. 문제 이해하기

길이가 N인 정수 배열 A와 B가 있습니다. 이 상황에서 함수 S는 다음과 같이 정의합니다.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열할 수 있습니다. 단, B에 있는 수는 재배열하면 안됩니다.

이 문제는 이러한 조건에서 S의 최솟값을 구하는 문제입니다.

A의 수를 재배열할 수 있지만 B에 있는 수는 재배열하면 안된다라… 이 문장을 기억하고 넘어가도록 하겠습니다.

그럼 입력, 출력, 제약 조건을 확인해보겠습니다.

• Input:
  • 첫째 줄에 N, 둘 째줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어집니다.
  • N은 50이하의 자연수이고, A와 B의 각 원소는 100이하의 음이 아닌 정수입니다.
    • 시간 복잡도에 영향을 주는 것은 N입니다. N이 매우 작기 때문에 시간 복잡도에 대한 고민은 안해도 될 것 같습니다.
    • 또한, 0이 아닌 자연수이므로 예외 케이스는 없습니다.
    • A와 B의 각 원소는 0이상 100이하의 정수입니다. 음수가 들어와서 규칙이 달라지지는 않을것으로 보입니다.
• Output:
  • S의 최솟값을 반환합니다.

이번 문제는 시간 복잡도에 대해 큰 고민은 안해도 될 것 같습니다. 그리고 예외 케이스도 없습니다. 이제, 조금더 자세하게 문제를 들여다 보겠습니다.

Step2. 문제 분석하기

이 문제는 그리디 알고리즘의 대표적인 예입니다. 그리디 알고리즘은 매 순간 최적의 선택을 함으로써 문제를 해결하려는 접근법입니다.

1. 핵심 아이디어:
   • 두 배열의 곱의 합 S를 최소화하기 위해서는 각 곱셈의 결과가 작아야 합니다.
   • 이를 위해 한 배열에서 가장 작은 값을 다른 배열의 가장 큰 값과 매칭하는 것이 최적의 선택입니다.
   • 이러한 방식은 각 단계에서 현재 상황에서 가장 최적의 선택을 하기 때문에 그리디 알고리즘의 정의에 부합합니다.
2. A의 재배열 가능성과 B의 고정:
   • 문제에서 A는 재배열할 수 있지만 B는 재배열할 수 없다는 조건이 있지만, 이는 A를 오름차순, B를 내림차순으로 정렬한 뒤 계산해도 문제의 제약을 만족합니다.

Step3. 코드 설계하기

• A는 오름차순으로 정렬합니다.
• B는 내림차순으로 정렬합니다.
• 두 리스트의 대응하는 원소를 곱하여 S를 계산합니다.
• 결과를 출력합니다.

Step4. 코드 구현하기

import sys

N = int(sys.stdin.readline().strip())

A = list(map(int,sys.stdin.readline().split()))
B = list(map(int,sys.stdin.readline().split()))

def sol(N, A, B):
    
    A.sort()
    B.sort(reverse=True)
    result = 0
    for i in range(N):
        result += A[i] * B[i]
    return result

print(sol(N=N, A=A, B=B))

코드 설명:

• 입력 처리:
  • N: 정수 배열의 크기
  • A, B: 두 배열로 입력받습니다.
• 정렬:
  • A.sort(): 오름차순 정렬로 작은 값을 앞에 배치.
  • B.sort(reverse=True): 내림차순 정렬로 큰 값을 앞에 배치.
• 최소값 계산:
  • 각 A[i]와 B[i]를 곱하여 누적 합산합니다.
• 출력:
  • 결과값을 출력합니다.

시간 복잡도:

• 정렬:
  • A.sort(): $O(N \log N)$
  • B.sort(reverse=True): $O(N \log N)$
• 곱셈 및 합산:
  • 한 번의 순회로 $O(N)$
• 최종 복잡도:
  • $O(N \log N)$

결과:

---

4. 마무리

핵심 요약

1. 이 문제는 그리디 알고리즘을 활용하여, 배열 간 최적의 매칭을 통해 S의 최솟값을 구하는 문제였습니다.
2. A는 오름차순, B는 내림차순으로 정렬한 뒤 각 원소를 곱하여 최소값을 구했습니다.
3. 정렬을 활용한 효율적인 접근으로 $O(N \log N)$ 시간 복잡도를 달성할 수 있었습니다.

배운 점

• 배열 정렬을 활용한 최적화 문제는 그리디 알고리즘의 대표적인 유형입니다.
• 문제의 조건(재배열 가능성)을 잘 이해하면 더 간단한 방식으로 문제를 풀 수 있다는 점을 확인했습니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!!

어제보다 발전된 나!