/ BOJ

BOJ_1026_보물_JAVA

문제 : 보물

링크 : BOJ_1026_보물

접근 방식

A와, B 배열에 각각 작위로 N개의 수가 들어가있다. B의 배치는 그대로 놔둔 채로 A의 배치를 바꾸어 A배열의 인자 * B배열의 인자를 모두 더한 값이 가장 작은 수 S를 구해야한다.

B를 재배치하지 말라는 문구가 함정이다. 이 문제의 출력은 값의 최소인 S만 출력하면 된다. 따라서, B의 가장 작은 수와 A의 가장 큰 수를 두고 곱하면 되는데, 이 때 A는 B의 최댓값의 맞은편에 A의 최솟값을 무슨 일이 있어도 놓을 수 있다. 따라서 B를 고정시켜둘 이유는 없어진다.

약간의 함정이 섞여들어있는 재미있는 문제이다. N이 50보다 작거나 같은 자연수임을 생각하면, 시뮬레이션 방식으로 풀어도 통과가 될 것 같기는 하다.

풀이 방법

  1. 먼저 배열의 크기를 읽어와 변수 N에 저장하고, N 크기의 배열 A, B를 생성한다.

  2. A와 B를 각각 정렬한다.

  3. 반복문을 돌리는데, A는 0부터, B는 N-1부터 시작하여 각각 +1, -1 해주며 서로 곱한 뒤 변수 S에 누적시켜준다.

  4. 반복이 모두 종료된 후 S를 출력한다.

소스 코드


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

class BOJ_1026_보물 {

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

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


		int N = Integer.parseInt(in.readLine());

		int[] A = new int[N];
		int[] B = new int[N];
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		StringTokenizer st2 = new StringTokenizer(in.readLine()," ");
		for(int i=0;i<N;i++) {
			A[i] = Integer.parseInt(st.nextToken());
			B[i] = Integer.parseInt(st2.nextToken());			
		}

		Arrays.sort(A);
		Arrays.sort(B);
		int S = 0;
		for(int i=0;i<N;i++) {
			S = S + A[i]*B[N-1-i];
		}
		System.out.println(S);

	}

}