[백준] #1026 보물

 문제

 

[문제 링크]

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

1026번: 보물

 

[문제]

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

길이가 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의 최솟값을 출력한다.

 

[예제 입출력]

[예제 입력 1 복사]

5
1 1 1 6 0
2 7 8 3 1

[예제 출력 1 복사]

18

 

[예제 입력 2 복사]

3
1 1 3
10 30 20

[예제 출력 2 복사]

80

 

[예제 입력 3 복사]

9
5 15 100 31 39 0 0 3 26
11 12 13 2 3 4 5 9 1

[예제 출력 3 복사]

528

 

 

 

 풀이 방법

 

[변수]

n : 배열 길이

a[], b[] : 각각 a, b 배열

cloneB[] : b배열을 복사한 배열

temp : 배열 정렬을 위해 필요한 배열 요소 임시 저장소

sum : 배열 곱의 합

 

 

[풀이]

Step1. a, b 배열을 입력받고 동시에 b 배열을 cloneB에 복사한다.

Step2. a 배열을 오름차순으로 정렬한다.

Step3. cloneB 배열을 내림차순으로 정렬한다.

Step4. 배열 a와 cloneB를 순서대로 곱하여 sum에 더해준다.

 

*정렬을 할 때 버블 정렬을 이용하였다.

 

 

 

 작성 코드

 

import java.lang.*;
import java.util.Scanner;

public class Treasure {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();    //배열 길이
        int a[] = new int[n];
        int b[] = new int[n];
        int cloneB[] = new  int[n];    //b배열 복사
        int i, j;
        int temp=0;
        int sum=0;
        
        //a, b 배열 입력 받기, cloneB에 b 복사
        for(i=0 ;i<n ;i++){
            a[i]=sc.nextInt();
        }
        for(i=0 ;i<n ;i++){
            b[i]=sc.nextInt();
            cloneB[i]=b[i];
        }

        //a 배열 오름차순으로 정렬
        for(i=0 ;i<n ;i++){
            for(j=0; j<n-i-1; j++){
                if(a[j] > a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        //cloneB 배열 내림차순으로 정렬
        for(i=0 ;i<n ;i++){
            for(j=0; j<n-i-1; j++){
                if(cloneB[j] < cloneB[j+1]){
                    temp=cloneB[j];
                    cloneB[j]=cloneB[j+1];
                    cloneB[j+1]=temp;
                }
            }
        }
        
        //a와 cloneB를 순서대로 곱하여 합 구하기
        for(i=0 ;i<n ;i++){
            sum+= a[i]*cloneB[i];
        }

        System.out.println(sum);

    }
}

 

* b배열을 복제하지 않고 b 배열의 값 크기 순서대로 a배열을 정렬하는 것도 해보기