[백준 1026번 문제, JAVA] 보물

문제

 

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

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

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

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

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

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");

        // A 배열을 입력받는다
        List<Integer> aList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            aList.add(Integer.parseInt(input[i]));
        }
        // A 배열을 정렬한다
        Collections.sort(aList);

        // B 배열을 입력받는다
        input = br.readLine().split(" ");
        List<Integer> bList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            bList.add(Integer.parseInt(input[i]));
        }

        // 임시로 A 배열을 저장할 C 배열을 만든다
        int[] cArray = new int[n];
        for (int i = 0; i < n; i++) {
            // B 배열에서 최대값을 받는다
            Integer max = Collections.max(bList);
            // 최대값의 인덱스를 받는다
            int index = bList.lastIndexOf(max);
            // 최대값 인덱스에 A 배열의 순서대로 값을 넣는다
            cArray[index] = aList.get(i);
            // B 배열에서 최대값을 제거한다
            bList.set(index, -1);
        }

        // B 리스트를 다시 원래대로 만든다
        for (int i = 0; i < n; i++) {
            bList.set(i, Integer.parseInt(input[i]));
        }

        // 최소값을 만든다
        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer += cArray[i] * bList.get(i);
        }

        System.out.println(answer);
    }
}

---

해결

A배열과 B배열을 모두 재배열 가능하면 더 쉽게 풀 수 있었겠지만 B는 재배열 하면 안된다는 양심의 규칙이 있다

사실 출력 결과만 보기 때문에 양심을 어겨도 괜찮은 사람은 A와 B를 모두 내림차순과 오름차순 각각 정렬해서

해당 함수의 정의대로 합을 구하면 될거다

 

A배열은 정렬을 하고 B배열의 최대값을 저장하고 그걸 다른 배열에 저장하면 A배열을 B배열에 따라서 저장이 가능하다

---

참고

링크