[ 𝗕𝗢𝗝 ] 1026번 보물 - 그리디(Greedy) | JavaScript

🎯 문제 설명

🧩 백준 1026번 - 보물|실버4

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

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

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

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄: N (N ≤ 50)
• 둘째 줄: A에 있는 N개의 수
• 셋째 줄: B에 있는 N개의 수
  • 0 < 각 원소 ≤ 100

5
1 1 1 6 0
2 7 8 3 1

출력

S의 최소값을 출력한다.

18

👩🏻‍💻 문제 풀이

A[i] * B[i] 의 총합을 최소로 만들기 위해서, B의 값이 클 수록 A의 작은 값이 곱해져야 합니다. (이 부분이 그리디 알고리즘입니다. 매 순간 A의 가장 작은 값을 B의 가장 큰 값 위치에 배치하는 겁니다.)

A배열은 오름차순으로, B배열은 내림차순으로 하여 순서대로 곱하면 쉽겠지만, 문제에서는 B배열의 순서는 바꿀 수 없다고 합니다. 따라서 정렬 대신 인덱스를 사용해 재배치 합니다.

우선, A배열을 오름차순으로 정렬합니다.

const arrA = input[1].split(' ').map(Number).sort((a, b) => a - b);

그 다음, B배열을 인덱스를 함께 저장하는 새로운 배열을 만들어서 내림차순으로 정렬합니다.

const arrB = input[2].split(' ').map(Number);
const indexB = arrB.map((val, idx) => ({val, idx})).sort((a, b) => b.val - a.val);

이렇게 하면 indexB배열은 다음과 같이 생겼습니다.

const indexB = [
	{val: 8, idx: 2},
	{val: 7, idx: 1},
	{val: 3, idx: 3},
	{val: 2, idx: 0},
	{val: 1, idx: 4}
]

이 배열의 idx 값을 가지고 arrA 배열을 정렬합니다.

const newA = [];
for (let i = 0; i < N; i++) {
  newA[indexB[i].idx] = arrA[i];
}

새로 정렬한 newA와 arrB 배열을 가지고 최소값 S를 구합니다.

let sum = 0;
for(let i = 0; i < N; i++){
    sum += newA[i] * arrB[i]
}

⊕ 덧1

사실 indexB를 구한 순간, 반복문을 돌면서 바로 sum을 구할 수도 있습니다. (이렇게 해도 통과됩니다.)

let sum = 0;
for (let i = 0; i < N; i++) {
  sum += arrA[i] * indexB[i].val;
}

하지만, 이 방식은 B배열을 정렬된 그대로 곱하는 방식이므로 문제의 핵심은 “B의 순서를 바꾸지 않고”에 어긋나게 됩니다. 즉, S = A[i] * B[i] + … 이라는 식대로 푼게 아니게 됩니다.

⊕ 덧2

그러면 결국 indexB도 B배열을 내림차순 정렬한 것과 똑같고, 이걸 사용했으면 정렬한 게 아닌가라는 의문이 듭니다. indexB는 B를 기준으로 정렬한 것은 맞지만 B배열을 정렬한 것은 아닙니다.

문제에서 금지하는 것은 B자체를 변경해서 A[i] * B[i] 를 위반하는 경우를 말합니다. 덧1의 방식처럼요.

indexB는 B의 복사본을 정렬한 것이고, 이에 맞게 A를 재정렬해 A[i] * B[i]를 맞췄다면 문제 조건에 위반하지 않습니다.

쉬운 예를 들자면, 학생들에게는 각자 반에서 번호가 있습니다. 그리고 학생들에게 점수에 따라 상품을 배정한다고 했을 때를 가정해봅시다. 학생들의 번호는 바꿀 수 없고, 점수 순으로 상품을 정한 뒤, 번호대로 배분해야 합니다.(보통 선생님들은 ’1번 김철수~, 2번 이영희~’ 이렇게 번호 순으로 호명하여 나누어줍니다.)

번호	학생	점수
1번	김철수	40
2번	이영희	60
3번	신짱구	20
4번	김도일	80

등수	상품
1등	10,000원
2등	5,000원
3등	3,000원
4등	1,000원

이 때, 점수를 기준으로 누가 몇 점인지 따로 정리한다고 해서 번호가 바뀌지 않습니다. 점수 순으로 상품을 정하고 원래 순서에 맞게 배분하면 됩니다.

점수	번호	상품
80	4번	10,000원
60	2번	5,000원
40	1번	3,000원
20	3번	1,000원

이렇게요.

번호	점수	상품
1번	40	3,000원
2번	60	5,000원
3번	20	1,000원
4번	80	10,000원

---

회고

사실, 최적의 방법을 찾아서 푼다고 푼건데 그리디를 생각하면서 풀지는 않아서 잘 모르겠다. 그리디라는 이론은 알겠는 데 문제풀이에는 써먹지 못하고 있는 기분이다.