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

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

 

algospot.com :: WEIRD

Weird Numbers 문제 정보 문제 In mathematics, weird numbers are natural numbers that are abundant but not semiperfect. In other words, a natural number N is a weird number if and only if: Sum of its proper divisors (i.e. less than N ) is greater than

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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() < 2throw 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, 00);
    }
 
    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 != 0continue;
            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);
    }
}
cs

 


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

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[CLOCKSYNC] Synchronizing Clocks  (0) 2022.01.02
[HAMMINGCODE] Hamming Code  (0) 2021.12.30
[XHAENEUNG] 째능 교육  (0) 2021.12.29
[URI] URI Decoding  (0) 2021.12.29
[BOARDCOVER] 게임판 덮기  (0) 2021.12.28
Posted by N'