[백준] 1026 보물 - Greedy / Java

• 문제 링크

1026번: 보물

 

• 풀이 과정

s 의 최솟값을 구하기 위해선 a 의 원소 중 가장 작은 값과 b 의 원소 중 가장 큰 값을 서로 곱하여 구한다.

따라서 b 에 있는 수를 재배열하면 안된는 문제 조건과 다르게 실제 구현 시 두 배열 모두 정렬이 필요하다.

 

정렬 후 a 는 오름차순을 따르고 b 는 역순으로 탐색하며, 각각의 값을 곱하여 sum 에 더한 후 정답으로써 출력한다.

 

• 풀이 코드

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

public 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));
        StringTokenizer st;

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

        int[] a = new int[n];
        int[] b = new int[n];

        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());

        Arrays.sort(a);
        Arrays.sort(b);

        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += a[i] * b[n - 1 - i];

        bw.write(String.valueOf(sum));
        bw.flush();
    }

}