https://www.acmicpc.net/problem/1026
문제
> 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다.
> 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
> 길이가 N인 정수 배열 A와 B가 있다.
> 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
> S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자.
> 단, B에 있는 수는 재배열하면 안 된다.
> S의 최솟값을 출력하는 프로그램을 작성하시오.접근
S의 값이 가장 작아지려면 가장 큰 값은 가장 작은 값과 곱해지고 그 다음 큰 값은 그 다음으로 작은 값과 곱해지는 과정을 반복해나가면 된다.
따라서 A는 오름차순, B는 내림차순(반대도 상관없음)으로 정렬한 뒤 순서대로 각각 곱해주면 된다.
문제해결
> 배열 A와 B에 해당하는 값을 입력받은 N을 크기로 하여 저장한다.
> A와 B를 오름차순 으로 정렬 한 뒤 S를 저장할 sum변수를 선언한다.
> 둘 다 오름차순이므로 A는 정방향, B는 역방향으로 인덱스를 잡아 곱해준 뒤 sum에 누적한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main
{
//1026번 보물
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], B = new int[N];
StringTokenizer st1 = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) A[i] = Integer.parseInt(st1.nextToken());
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) B[i] = Integer.parseInt(st2.nextToken());
Arrays.sort(A);
Arrays.sort(B);
int sum = 0;
for(int i = 0; i< N; i++) sum += A[i] * B[N-1-i];
System.out.print(sum);
}
}후기
B는 재배열 하면 안된다 라는 말에 사로잡혀 이걸 하나하나 다 경우를 따지며 매칭 시켜? 라는 생각을 하며 이것저것 생각해 봤다. 하지만 가장 좋은 방법은 각각 내림, 오름차순으로 정렬하고 곱해주는 것이다. 일단 문제에서 원하는 출력이 각 배열의 상태가 아니고 암튼 곱한 값의 최소를 원하니까 그냥 정렬해도 티 안나 라는 마음으로 B도 정렬해서 계산했다. 제출 해보니 맞아서 그게 맞구나 했다.
