[WEIRD] Weird Numbers
개발이야기/알고스팟2021. 12. 30. 11:33
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() < 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);
}
}
|
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 |