Power Coding 파워 코딩

Knapsack

09 May 2019 Tags:
HackerRank, Dynamic Programming


Knapsack

주어진 배열로 목표 합을 배열의 원소를 0번 또는 여러번 사용하여 넘치지 않고 가장 근접한 합을 만들어 리턴!!

ex) arr=[2,3,4] target sum = 10 인경우
[2,2,2,2,2] , [2,2,3,3], 등..

input
t
n k
배열 원소들

t : test case 수
n : 배열 사이즈
k : 목표 합

제약조건
1 <= t <= 10
1 <= n,k,arr[i] <= 2000

풀이 과정

먼저 심플하게 생각해 보면 모든 경우의 수를 다 해보면 풀릴 것 같다.

또한, 예시 입력을 봤을 때에도 arr[i]의 각 원소는 중복 될 수 있다.

모든 경우의 수를 다 해보면 비 효율적이므로,

첫 번째로 할만한 경우는 더하지 않고 가능한 경우이다.

어떤 수를 나눈 나머지가 0 인경우 더해볼 필요가 없다. 그럼 어떻게 나눠야 할까?

소수 구하는 방법처럼 2, 3의 곱들을 제거 해 보았다.

또한 2+3 = 5의 경우도 만들어질 수 있으므로, 제거해 보았다.

그런데 23같은 경우 2x10+3이므로 23도 지워져야 된다. 따라서, 곱셈만으로는 구하기 어려워 보인다.

이 때문에 효율적으로 모든 경우의 수를 더하여 체크한는 방법을 생각해 보았다.

재귀적으로 현재 수에서 배열의 수를 순차적으로 더하는 방법이 가능하다.

그런데, 제약 조건을 봤을 때, n,k,arr[i]이 2000이다. 사이즈가 굉장히 적다.

사이즈가 굉장히 적기 때문에, flag를 두어서 이미 체크한 경우를 생각할 수있다.

그래서 중복으로 함수를 call 할필요 없게 만들 수 있다.

또한, 입력의 중복된 원소를 제거하기 위해 오름차순으로 정렬을 한다음 중복되는 수는 제거해 준다.

풀이 핵심

  1. 제약조건이 낮기 때문에, 심플하게 재귀적으로 모든 수를 더하여 체크할 수 있다.
  2. 제약조건이 낮기 때문에, flag를 두어 중복 체크를 방지 가능

Algorithm

  1. 입력받은 수를 오름차순으로 정렬한다.
  2. 중복된 입력은 제거 한다.
  3. 재귀적으로 0부터 입력을 모두 더하여 체크 한다.

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the unboundedKnapsack function below.
    static final int  maxInput = 2000;
    static int checkMax = 0;
    
    static void check(boolean[] isChecked, ArrayList<Integer> al, int cur, int target) {
        
        if(cur > target || cur > isChecked.length) return;
        
        if(isChecked[cur]) {
            return;
        }
        
        isChecked[cur] = true;
        
        if(checkMax < cur ) checkMax = cur;
        
        for(int e : al) {
            check(isChecked, al, cur+e, target);
        }
        
    }
    
    static int unboundedKnapsack(int k, int[] arr) {
         ArrayList<Integer> al = new ArrayList<>(); 
         boolean[] isChecked = new boolean[maxInput +1];
         checkMax = 0;
            
         Arrays.sort(arr);
         
         int i = 0;
         int before = 0;
         for(int e : arr) {
             if(before == e) {
                 continue;
             }
             
             al.add(e);
             before = e;
         }
         
         check(isChecked, al, 0,k);
         
         return checkMax;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
          BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
        for(int test = 0; test < t; test++) {
            String[] nk = scanner.nextLine().split(" ");

            int n = Integer.parseInt(nk[0]);

            int k = Integer.parseInt(nk[1]);

            int[] arr = new int[n];

            String[] arrItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int arrItem = Integer.parseInt(arrItems[i]);
                arr[i] = arrItem;
            }

            int result = unboundedKnapsack(k, arr);
            System.out.println(result);
            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }
        
        bufferedWriter.close();

        scanner.close();
    }
}

Related Posts