[boj] 1026번: 보물

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

1026번: 보물

 

 

 

1. 문제 설명 

길이가 N인 정수 배열 A와 B가 있고, 다음과 같이 함수 S가 정의된다.

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

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안된다.

S의 최솟값을 출력하라.

 

 

 

2. 접근 방식 

사실 문제에서 B에 있는 수를 재배열하지 말라고 했지만 출력은 S의 최솟값을 출력하는 것이라 B를 재배열해도 문제가 되지 않는다. 

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

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 Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;


        Integer[] A = new Integer[n];
        Integer[] B = new Integer[n];

        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, Collections.reverseOrder());
        Arrays.sort(B);
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans += A[i] * B[i];
        }
        System.out.println(ans);
    }
}

 

 

4. 분석

1. Time : O(nlogn) 
2. Space :
3. 소요시간 : 30분 
4. 제출 횟수 (무작정 제출하기 않기)  : 2회
5. 어려웠던 부분과 해결한 방법 : 처음에는 B에 있는 수를 재배열하지 않고 접근하려다 틀렸다. 그러다 어차피 최솟값을 출력하는데 B를 재배열하든 말든 문제가 될까? 라는 생각에 재배열시키고 통과한 케이스이다.
6. 실수가 줄어들었는가 ? 요즘 실수를 줄이기 위해 연습중이다...