[백준/자바] 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

 

 

 

풀이

[입력]

A와 B에 대해 따로 ArrayList를 만들어 값을 넣는다.

 

[로직]

A는 오름차순 정렬, B는 내림차순 정렬을 한다. A에는 Collections.sort()로 오름차순 정렬을 적용하면 된다. B는 오름차순으로 정렬 후 뒤집으면 내림차순 정렬이 된다. 따라서 B에는 Collections.sort() 후 Collections.reverse()를 적용하면 된다.

이후 ArrayList의 size만큼 돌면서 각 ArrayList의 원소들을 서로 곱해서 answer에 누적하면 된다.

 

 

코드

package baekjoon._1026;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    public static int solution(ArrayList<Integer> arrA, ArrayList<Integer> arrB) {

        int answer = 0;

        Collections.sort(arrA); // 오름차순 정렬
        Collections.sort(arrB); // 오름차순 정렬
        Collections.reverse(arrB); // 반대로 뒤집기 -> 내림차순 정렬

        for(int i = 0; i < arrA.size(); i++) {
            answer += arrA.get(i) * arrB.get(i);
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> arrA = new ArrayList<>();
        ArrayList<Integer> arrB = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            arrA.add(Integer.parseInt(st.nextToken()));
        }

        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            arrB.add(Integer.parseInt(st.nextToken()));
        }

        bw.write(sb.append(solution(arrA, arrB)).toString());
        bw.flush();
        bw.close();
        br.close();

    }
}