[Java] 백준(실버-4) 1026번 - 보물

문제 풀이

---

이 문제는 배열 정렬을 통해 풀 수 있는 간단한 문제이다.

아이디어 도출

A 배열과 B 배열을 어떻게 정렬해야 A[0]*B[0]+...+A[N]*B[N]의 값을 최소로 할 수 있을까?

조금만 생각해보면 쉽게 알 수 있다. 바로 곱해지는 수를 작게 만들면 된다. 아래 예시를 보자.

5
1 1 1 6 0 
2 7 8 3 1
= 2+7+8+18+1 = 35

// A 배열은 내림차순으로, B 배열은 오름차순으로 정렬
5
6 1 1 1 0
1 2 3 7 8
= 6+2+3+7+0 = 18 

위처럼 곱해지는 수가 작게 되도록 A 배열은 내림차순으로, B 배열은 오름차순으로 정렬하여 S 함수식을 적용하니 최솟값을 구할 수 있었다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        Integer[] A = new Integer[N];
        int[] B = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        /**
         * A, B 배열 정렬
         * (A[0]*B[0])+(A[N]*B[N]) 값을 최소로 만드러면 B 원소의 최대값일 수록 작은 값을 곱해야 한다.
         * 이를 위해 B를 오름차순으로 정렬한 뒤, A를 내림차순으로 정렬한다.
         * 이때, A를 내림차순 정렬하기 위해 Integer형의 배열로 사용한다.
         */
        Arrays.sort(A, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        Arrays.sort(B);

        int result = 0;
        for(int i=0; i<N; i++) {
            result += A[i] * B[i];
        }

        bw.write(result+"\n");

        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.