[WEIRD] Weird Numbers

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/WEIRD

algospot.com :: WEIRD

풀이입니다. 🤔

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            System.out.println(isWeird(scanner.nextInt()) ? "weird" : "not weird");
        }
    }
    
    private static boolean isWeird(int n) {
        List<Integer> divisors = getDescSortedDivisors(n);
        if (divisors.size() < 2) throw new IllegalArgumentException("N was not greater than 1");
        
        return isWeird(divisors.remove(0), divisors);
    }
 
    private static boolean isWeird(int n, List<Integer> divisors) {
        // Condition 1 : Sum of its proper divisors (i.e. less than N ) is greater than the number.
        int sum = 0;
        for (Integer divisor : divisors) {
            sum += divisor;
        }
        if (sum < n) return false;
 
        // Condition 2 : No subset of its divisors sum to N.
        return !hasSumOfDivisorsToN(n, divisors, 0, 0);
    }
 
    private static List<Integer> getDescSortedDivisors(int n) {
        List<Integer> ret = new ArrayList<>();
        for (int i = (int) Math.sqrt(n); i >= 1; --i) {
            if (n % i != 0) continue;
            int divide = n / i;
            if (divide == i) ret.add(divide);
            else {
                ret.add(0, divide);
                ret.add(i);
            }
        }
 
        return ret;
    }
 
    private static boolean hasSumOfDivisorsToN(int n, List<Integer> divisors, int acc, int cur) {
        if (n == acc) return true;  // 기저사례 1 : 누적된 덧셈이 n 가 동일한가? (N 을 구성할 수 있는 Subset 존재)
        if (n < acc) return false;  // 기저사례 2 : 누적된 덧셈이 n 보다 큰가? (해당 경우의 수는 더 살펴보지 않음)
        if (divisors.size() <= cur) return false; // 기저사례 3 : index 가 약수의 개수를 초과 (경우의 수 끝에 도달)
 
        // 각 index 의 숫자를 포함하는 경우와 아닌 경우에 따라 완전탐색을 한다.
        // 큰 수를 먼저 덧셈하기 때문에, 기저사례2 에 먼저 도달할 수 있도록 처리한다.
        return hasSumOfDivisorsToN(n, divisors, acc + divisors.get(cur), cur + 1)
                || hasSumOfDivisorsToN(n, divisors, acc, cur + 1);
    }
}

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️