그리디: 보물 (백준 1026)

○ 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 48381 31588 26899 67.652%

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

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

---

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//배열 길이 입력
		int res = 0;
		int len = sc.nextInt();
		
		//배열 A, B 입력
		int[] a = new int[len];
		int[] b = new int[len];
		
		for (int i = 0; i < len*2; i++) {
			if (i < len)
				a[i] = sc.nextInt();
			else
				b[i-len] = sc.nextInt();
		}

		//A, B 재배열
		Arrays.sort(a);
		Arrays.sort(b);
		
		for (int i = 0; i < len; i++) {
			res += a[i] * b[len-i-1];
		}
		
		System.out.println(res);

	}
	
}

○ 확인
- 인덱스를 잘 확인하자..