S = A[0] * B[0] + ... + A[N - 1] * B[N - 1]

- S의 값을 가장 작게 만들기 위해 A의 수를 재배열
- 단, B에 있는 수는 재배열하면 안 됨
- S의 최솟값을 출력하는 프로그램

- 큰 수 * 작은 수
A: 1 1 1 6 0 (재배열 O)
B: 2 7 8 3 1 (재배열 X)

=> 1 * 2 + 1 * 7 + 0 * 8 + 1 * 6 + 1 * 3
=> 2 + 7 + 6 + 3 = 18

B의 maxIdx, minIdx 를 찾아서 A의 재배열한 minIdx, maxIdx와 일치시켜줘야 함
Markdown
복사

•

문제를 처음보고 알았다. 최솟값을 구해야 하는데 배열이 두 개인 경우라면 큰 수와 작은 수를 곱했을 때 최솟값이 나올 것이라는 생각이 딱 들었다.

•

문제에서는 A의 수를 재배열하고 B에 있는 수는 재배열하면 안 된다고 하였다.

해결 방법

•

리스트를 활용하여 최댓값, 최솟값을 비교하는 로직을 구현한다.

•

A의 수가 담긴 리스트만 정렬한다.

•

최댓값, 최솟값을 찾으면 해당 인덱스의 값을 기존 리스트에서 제거한다.

•

제거한 리스트의 길이를 고려하여 반복문을 구성한다.

코드

package algo250223;

import java.io.*;
import java.util.*;

// 보물 - 실버 4
public class Baek1026 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int aN = N;
        int bN = N;

        // 각각의 리스트 선언
        List<Integer> aList = new ArrayList<>();
        List<Integer> bList = new ArrayList<>();

        // A 리스트 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            aList.add(Integer.parseInt(st.nextToken()));
        }

        // A 리스트 재배열
        Collections.sort(aList);

        // B 리스트 입력
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            bList.add(Integer.parseInt(st.nextToken()));
        }

        int max = Integer.MIN_VALUE;        // 최댓값 선언 및 초기화
        int min = Integer.MAX_VALUE;        // 최솟값 선언 및 초기화
        int sum = 0;                        // 결과값 선언 및 초기화

        int aIdx = 0;
        int bIdx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < aN; j++) {
                if (min > aList.get(j)) {
                    aIdx = j;
                    min = aList.get(aIdx);
                }
            }

            min = aList.remove(aIdx);       // 리스트에서 최솟값 제거

            for (int k = 0; k < bN; k++) {
                if (max < bList.get(k)) {
                    bIdx = k;
                    max = bList.get(bIdx);
                }
            }

            max = bList.remove(bIdx);       // 리스트에서 최댓값 제거

            sum += min * max;
            min = Integer.MAX_VALUE;        // 최솟값 초기화
            max = Integer.MIN_VALUE;        // 최댓값 초기화
            aN--;                           // A 리스트 길이를 고려하여 aN 감소
            bN--;                           // B 리스트 길이를 고려하여 bN 감소
        }

        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
        br.close();
    }
}
Java
복사

다른 풀이의 코드

•

이 풀이 같은 경우 A와 B를 모두 재배열 하였는데 시간은 내 코드에 비해 다소 빨리 나오기는 했지만 조건을 충족하지 않았다. 다만 이 코드 역시 큰 수와 작은 수를 곱하면 최솟값을 구할 수 있는 아이디어에 착안하여 코드를 작성하였다.

package algo250223;

import java.io.*;
import java.util.*;

// 보물 - 실버 4, 다른풀이
public class Baek1026_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N];
        int[] B = new int[N];

        StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st1.nextToken());
            B[i] = Integer.parseInt(st2.nextToken());
        }

        Arrays.sort(A);
        Arrays.sort(B);

        int result = 0;

        for (int i = 0; i < N; i++) {
            result += A[i] * B[N - 1 - i];
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}
Java
복사