[백준 JAVA] 1026 : 보물

[백준 1026] 보물 : https://www.acmicpc.net/problem/1026

1026번: 보물

---

문제 조건 정리

 

1. S = A[0] × B[0] + ... + A[N-1] × B[N-1] 
   S의 값을 최소화하자.

---

입력

 

1. 첫째 줄에 N이 주어진다.
2. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어진다.
3. 셋째 줄에는 B에 있는 수가 순서대로 주어진다.
4. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

---

문제를 풀기 전

 

1. S = A[0] × B[0] + ... + A[N-1] × B[N-1]
   -> S를 최소화하기 위해서는 A배열의 가장 작은 값과 B배열의 가장 큰 값을 곱할 수 있도록 배치해야한다!
   -> 오름차순으로 정렬된 배열과 내림차순으로 정렬된 배열을 곱해야겠다!
   -> 오름차순으로 정렬된 배열의 i번째 요소와 오름차순으로 정렬된 배열의 (N-i-1)번째 요소를 곱해도 되겠다!

---

코드

 

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

public class Main {

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());

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

        // a 배열과 b 배열의 값을 입력받음
        StringTokenizer stringTokenizer1 = new StringTokenizer(bufferedReader.readLine(), " ");
        StringTokenizer stringTokenizer2 = new StringTokenizer(bufferedReader.readLine(), " ");
        
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(stringTokenizer1.nextToken());
            b[i] = Integer.parseInt(stringTokenizer2.nextToken());
        }

        // a 배열과 b 배열을 오름차순으로 정렬함
        Arrays.sort(a);
        Arrays.sort(b);

        // 결과값 저장을 위한 변수
        int res = 0;

        // a 배열의 i번째 요소와 b 배열의 n-i-1번째 요소를 곱한 값을 res 에 더함
        // ex) n이 5라면 (0 ~ 4) -> 0번째 요소와 4번째 요소를 곱한 값을 res에 더함
        for (int i = 0; i < n; i++) {
            res += a[i] * b[n - i - 1];
        }

        // 결과 출력
        System.out.println(res);
    }
}

 

---

문제를 풀고 난 후

 

그리디 알고리즘을 이해하기에 매우 직관적인 문제라고 생각함!

알고리즘과 상관없이 문제를 풀며 배운 점이 있었는데, stringTokenizer를 두개 이상 사용해서 동시에 입력을 받을 수 있다는 점이다!