[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1026번, 보물

문제 링크

1026번: 보물

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 함수 S에 대한 정의가 주어집니다.

2. A의 수를 재배열해야 하며, B의 있는 수는 재배열하지 말아야 한다.

3. S 함수에 최소값을 구해서 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. A와 B의 값을 정렬하여 함수 S를 진행합니다.

 

3. S를 진행한 값을 결과로 출력합니다.

 

함수 S.

 

함수 S  = A[0] × B[0] + ...  + A[N-1] × B[N-1]

 

함수 S가 최소값을 가지려면 A의 큰 값과 B의 작은 값이 서로 곱해져야 합니다.

 

A는 오름차순 정렬, B는 내림차순 정렬을 한 뒤에

 

함수 S를 진행하면 최소값을 구하실 수 있습니다.

 

예를 들어.

A	2	4	5
B	0	3	2

정렬 진행

A	2	4	5
B	3	2	0
	6	8	0

최소값 : 6 + 8 + 0 = 14를 구하실 수 있습니다.

 

※문제에서 "B를 재배치 시키면 안된다고 했는데 정렬을 사용하면 안되지 않나요?" 질문이 생기실 수 있는데 B를 정렬하는 것은 재배치를 시키는 것이 아니라 짝을 찾아주는 것이라고 생각하시면 됩니다.

 

코드에서는 정렬해서 재배치하는 것처럼 느끼실 수 있지만 그림으로 표현하면

A	5(0의 짝)	2(3의 짝)	4(2의 짝)
B	0	3	2

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 5

A	1	1	1	6	0
B	2	7	8	3	1

 

2. A와 B의 값을 정렬하여 함수 S를 진행합니다.

 

A는 오름차순, B는 내림차순 정렬 진행!

 

A	0	1	1	1	6
B	8	7	3	2	1

함수 S 진행!

 

A	0	1	1	1	6
B	8	7	3	2	1
	0	7	3	2	6

최소값 : 0 + 7 + 3 + 2 + 6 = 18

 

3. S를 진행한 값을 결과로 출력합니다.

 

18을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer와 input함수를 통해서 A[]와 B[]의 입력값을 저장합니다.
• Arrays.sort를 이용하여 A[], B[] 배열을 정렬하였습니다.
• for문을 이용하여 함수 S를 진행하여 결과를 얻었습니다.
• 함수 S의 결과를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• input함수는 매개변수로 받은 StringTokenizer를 이용하여 배열에 저장합니다.

 

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


public class Main {
    static int N;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        Integer[] A = new Integer[N];
        Integer[] B = new Integer[N];
        st = new StringTokenizer(br.readLine()," ");
        //A[] 설정
        input(A, st);
        st = new StringTokenizer(br.readLine()," ");
        //B[] 설정
        input(B, st);
        Arrays.sort(A);		//A 오름차순 정렬
        Arrays.sort(B, Collections.reverseOrder());	//B 내림차순 정렬
        int answer = 0;
        //함수 S 진행
        for(int i=0;i<N;i++)
            answer += A[i] * B[i];
        bw.write(answer + "");		//결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //입력값을 배열에 저장하는 함수
    static void input(Integer[] arr, StringTokenizer st){
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());
    }
}