[BaekJoon] 백준 1026번 _ 보물 for JAVA _ 그리디 알고리즘

 

https://www.acmicpc.net/problem/1026

1026번: 보물

 

 

문제

 

 

---

 

A[0] x B[0] + A[1] x B[1] + ... A[N-1] x B[N-1] 의 값이 최소값이 되기 위해서는

 

A의 가장 작은 수 x B의 가장 큰 수

 

이런식으로 곱셈이 되어야 한다.

 

 

문제에서 A의 배열속 값만 움직일 수 있다고 했지만

 

B도 같이 움직여줘도 된다. 왜냐면 큰거 x 작은거가 되는 계산값..은 같으니까....

 

순서가 중요하지 않으므로 A는 오름차순, B는 내림차순으로 정렬해서 계산하면 된닷

 

 

 

코드

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


public class Baek1026 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];
		Integer[] B = new Integer[N]; // 내림차순 정렬 해줘야해서 int말고 Integer라고 선언해줌
		
		
		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 count = 0;
		
		for(int i = 0; i < N; i++)
			count += (A[i] * B[i]);
		
		System.out.println(count);
	}

}

 

 

오름차순은 그냥 Arrays.sort(A) 해주면 되고

 

 

내림차순은 Arrays.sort(B, Collections.reverseOrder()) 로 해줘야한다.

 

그리고 내림차순을 할 때 B[]의 자료형이 int값이면 오류가 뜨므로 Wrapper 클래스인 Integer를 사용해야 한다.!

 

 

 

 

 

성능