[백준 - 1026] 보물 - Java

문제 설명

 

1026번: 보물

 

접근 방법

해당 문제는 그리디 알고리즘 기법을 이용하여 해결할 수 있었습니다.

 

사실 이 문제를 처음 봤을 때 시간 제한이 2초이길래 A에 있는 N개의 수를 재배열할 수 있는 모든 경우의 수에 대해 완전 탐색하여 구해도 되겠다는 생각을 했었습니다. 그리하여 백트래킹을 통해 각각의 경우에 수에 대해 최솟값을 구하도록 했으나, 결과는 시간 초과였습니다. 😅

 

N은 50보다 작거나 같은 자연수이긴 하지만 이들을 순열로 재배열한다는 것은 50!라는 엄청난 수에 대해 탐색하는 것이기 때문에 매우 비효율적인 방법이었습니다.

 

그리하여 접근 방법을 달리하여 어떻게 하면 최솟값을 구할 수 있을지 생각해봤는데, 좀만 생각해보니 A를 오름차순으로 정렬하고 B를 내림차순으로 정렬한 이후에 각각의 요소별로 곱해주고 누적하여 더한다면 그 값이 최솟값이었습니다. 개인적인 직관으로 따져보았을 때는 곱셈 연산 시 B의 최댓값을 A의 최솟값으로 무마시켜 최대한 값을 억제시키 수 있겠다 생각했습니다.

 

전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        Integer[] b = new Integer[n];

        StringTokenizer 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, Comparator.reverseOrder());

        int result = 0;
        for (int i = 0; i < n; i++) {
            result += a[i] * b[i];
        }

        System.out.println(result);
    }
}

 

(번외) 백트래킹을 통한 풀이 - 시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

class Main {

    static int n, result = 500000;
    static Stack<Integer> numbers = new Stack<>();
    static int[] a, b;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a = new int[n];
        b = new int[n];

        StringTokenizer 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());
        }

        boolean[] visited = new boolean[n];
        arrange(0, visited);

        System.out.println(result);
    }

    private static void arrange(int depth, boolean[] visited) {
        if (depth == n) {
            result = Math.min(result, getSum());
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                numbers.push(a[i]);
                arrange(depth + 1, visited);
                visited[i] = false;
                numbers.pop();
            }
        }
    }

    private static int getSum() {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += numbers.get(i) * b[i];
        }
        return sum;
    }
}

 

참고자료

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