[ABC251] B - At Most 3 (Judge ver.) (AtCoder Beginner Contest 251 in Java)

문제 : abc251_b

 

  1~3개의 합이 W이하인지 확인하는 문제이다. 최소 1개, 최대 3개를 모두 골라보면 된다. 따라서 모든 경우를 확인하는데 O(N^3)이 필요하며, N이 최대 300개이므로 시간은 널널하다. 중간에 합이 W보다 커지는 경우 해당 경우를 확인하지 않는 백트래킹 개념도 더하면 더 효율적으로 짤 수 있다.

 

  주의점은 모든 경우 중, W이하를 만족하는 모든 경우를 구하는게 아니라 그러한 합계를 구해야 한다. 따라서 HashSet 등을 통해 중복된 값은 카운팅 하지 않도록 별도로 처리가 필요하다.

 

코드 : github

...
int n, w, ans=0;
int[] arr;
boolean[] v;
HashSet<Integer> hs = new HashSet<>();
private void proc(int idx, int sum) {
    if (sum > w) return;
    if (sum != 0 && !hs.contains(sum)) {
        hs.add(sum);
        ans++;
    }
    if (idx == 3) return;

    for (int i = 0; i < n; i++) {
        if (v[i]) continue;
        v[i] = true;
        proc(idx+1, sum+arr[i]);
        v[i] = false;
    }
    proc(idx+1, sum);
}
private void solution() throws Exception {
    n = nextInt();
    w = nextInt();
    arr = new int[n];
    v = new boolean[n];
    for (int i = 0; i < n; i++) arr[i] = nextInt();
    proc(0, 0);
    System.out.println(ans);
}
...