[백준] 1026 : 보물 (JAVA)

난이도

🥈 4

 

링크

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

1026번: 보물

---

문제

---

풀이과정

해당 문제는 그리디 알고리즘을 사용해서 푸는 문제였다. 

 

사실 다른 그리디 문제들과는 달리 A의 수를 재배열하고, B에 있는 수를 재배열하지 말라고 했지만,     

그저 'S의 최솟값'을 출력하기만 하면 되기에 둘 다 정렬하여 결과값을 구했다 :)

 

1) 각각 입력받은 값들을 A와 B 배열에 저장한다.

2) A 배열은 오름차순으로, B 배열은 내림차순으로 정렬한다.

3) i번에 해당하는 A와 B 배열의 값을 곱한 값을 더해 최솟값을 구한다.

 

위의 과정만 수행하면 끝나는 문제였다! (그리디라고 할 수 있을까..ㅎㅎ) 

 

🚨 B 배열에서 내림차순 정렬할 때 int 배열이 아닌 Integer 배열을 써야한다!

      (Collection은 객체만 타입으로 가질 수 있기 때문에..)

      (reverseOrder() 함수 대신 lamda를 사용하면 더 편하게 정렬 가능!) 

---

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] A = new int[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);
        Arrays.sort(B,Collections.reverseOrder());

        int count = 0;

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

        System.out.println(count);
    }
}

 

결과