[BOJ/JAVA] 백준 1026 : 보물 (자바)

문제 정보

  문제명   - 보물
  난이도   - 실버 IV
문제 번호 - 1026번

---

문제 링크

BOJ_S4_1026_보물

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

---

예제 입력/출력

예제 입력	예제 출력
5 1 1 1 6 0 2 7 8 3 1	18
3 1 1 3 10 30 20	80
9 5 15 100 31 39 0 0 3 26 11 12 13 2 3 4 5 9 1	528

---

힌트

예제 1의 경우 A를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.

---

알고리즘 분류

● 수학
● 그리디 알고리즘
● 정렬

---

소스코드

package Lv2_Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 수학, 그리디 알고리즘, 정렬
 * https://www.acmicpc.net/problem/1026
 */
public class BOJ_S4_1026_보물 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(br.readLine());
		int S = 0;
		int[][] AB = new int[2][N];
		for (int i = 0; i < 2; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				AB[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		Arrays.sort(AB[0]);
		Arrays.sort(AB[1]);
		for (int i = 0; i < N; i++) {
			S += AB[0][i] * AB[1][N-1-i];
		}
		System.out.println(S);
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---