728x90
반응형
1026 - 보물
https://www.acmicpc.net/problem/1026
문제
길이가 N인 정수 배열 A, B
$S = A[0] * B[0] + \dots + A[N-1] * B[N-1]$
S의 값을 가장 작게 만들기 위해 A의 수를 재배열
(단, B에 있는 수는 재배열 X)
=> S의 최솟값을 출력
입력
첫째 줄: N
둘째 줄: A에 있는 N개의 수 순서대로 주어짐
셋째 줄: B에 있는 수가 순서대로 주어짐
N (자연수) <= 50, A, B (음이 아닌 정수) <= 100
출력: S의 최솟값
풀이
- `Arrays.sort(A)`
- A: 오름차순 정렬
- `Arrays.sort(B, Collections.reverseOrder())`
- B: 내림차순 정렬
예시
A = [1, 1, 1, 6, 0]
B = [2, 7, 8, 3, 1]
-> A = [1, 1, 0, 1, 6]과 같이 재배열하면 최솟값
=> A의 가장 작은 값 * B의 가장 큰 값 / A의 가장 큰 값 * B의 가장 작은 값
코드
import java.io.*;
import java.util.*;
// 보물
public class boj_1026 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Integer[] A = new Integer[N];
Integer[] B = new Integer[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());
}
Arrays.sort(A);
Arrays.sort(B, Collections.reverseOrder());
int sum = 0;
for (int i = 0; i < N; i++) {
sum += A[i] * B[i];
}
System.out.println(sum);
}
}
728x90
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[BOJ/Greedy] 백준 2457 - 공주님의 정원 (Java) (0) | 2025.04.27 |
---|---|
[BOJ/Greedy] 백준 11399 - ATM (Java) (0) | 2025.04.27 |
[BOJ/Greedy] 백준 2217 - 로프 (Java) (0) | 2025.04.27 |
[BOJ/Greedy] 백준 1931 - 회의실 배정 (Java) (0) | 2025.04.27 |
[BOJ/Greedy] 백준 11047 - 동전 0 (Java) (0) | 2025.04.27 |