[BOJ] 백준 1026번 : 보물 (JAVA)

문제

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

길이가 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의 최솟값을 출력한다.

 

풀이

정렬을 이용하여 풀 수 있는 문제였습니다. 문제에서는 A와 B 배열이 주어지는데, 이 두 배열의 각각의 요소를 서로 곱해서 더한 값이 최소로 만들어야했습니다. 그리고 A는 위치를 바꿔도 되지만, B는 위치를 바꾸면 안 되는 조건이 있습니다. 표면적으로는 B는 냅두고 A만 어떻게 이리저리 바꿔야만 할 것처럼 보입니다. 하지만, 무조건적으로 A만 고려할 필요는 없습니다.

문제의 예시를 가지고 설명하겠습니다.

 

A = {1, 1, 1, 6, 0}

B = {2, 7, 8, 3, 1}

 

일 때, A = {1, 1, 0, 1, 6}일 경우 최소라고 명시되어 있습니다.

여기서, B의 가장 큰 값이 A의 가장 작은 값과 매치가 되고, B의 2번째로 큰 값이 A의 2번째로 작은 값과 매치가 된다는 사실을 알 수 있습니다.

따라서, A를 오름차순으로 정렬한 후, B를 내림차순으로 정렬하여 이 둘의 각각의 요소를 곱해서 더해 나가면 됩니다.

참고로, Arrays.sort를 이용하여 오름차순으로 정렬할 경우, primitive 타입을 사용해도 되지만, 내림차순을 정렬할 경우, Wrapper 클래스를 이용해야 합니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        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];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A); // A를 오름차순으로 정렬
 
        Integer[] B = new Integer[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(B, Comparator.reverseOrder()); // B를 내림차순으로 정렬
 
        int ans = 0;
        for (int i = 0; i < N; i++) { // A의 가장 작은 값과 B의 가장 큰 값을 곱해서 더해 나감.
            ans += A[i] * B[i];
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}
 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.