[algospot]WEIRD

문제

https://algospot.com/judge/problem/read/WEIRD

weird number (http://en.wikipedia.org/wiki/Weird_number)

A natural number that is abundant but not semiperfect; one for which the sum of the proper divisors (including 1 but not itself) is greater than the number, but no subset of those divisors sums to the number itself.

위키검색결과......뭔소리지;; 어렵다...번역기를 돌려봐도 ... 뭥미

해석해보자면 

충만하지만 not semiperfect한 자연수이다. semiperfect라...뭐지...그분을 불러야겠다.  구글신에게 물어봤다.

 

http://mathworld.wolfram.com/PseudoperfectNumber.html 첫줄에보면 semiperfect라고 불리는 pseudoperfect number

 

는 Benkoski씨가 발견했나? 하여튼 뜻은 약수의 합이 자기 자신과 같은 양의정수 라고한다.

 

그리고 자기자신을 제외하고 1을 포함한 약수의 합이 자신보다 큰수이고 약수의 합이 자기자신이 되는 조합이 하나도 없는 수!

 

첫줄에서 멘붕해서 검색해놨더니 뒤에 다 나오네;;;그러하답니다.

입력

1부터 5만 이하

 

출력

'weird' or 'not weird'

 

풀이

풀이 계획은 

1. 약수를 구한다. 

2. 약수의 조합을 이용해서 약수의 합을 검사해나간다. 

3. 조건을 검사해서 결과를 구한다.

위와 같이 코딩을 하고 돌렷다. 결과 잘나왔다. 하!지!만!.입력 최대값 넣으니까 여지없이 뻗었다.여지없이...

반복수가 너무 많아서 뻗는다고 결론짓고 약수구하는 for문에서 시작값을 입력값/2 부터 시작하게 적용했다.

약수하는 for문 subset구하는 for문을 하나로 합쳤다.

약수를 구해가면서 약수의 합도 같이 구해간다.  구한 약수를 합에 더했을때 자신보다 크면 다시빼고 작으면 다음 약수를 구한

다. 약수를 다구할때까지 진행해서 자신과 같아지지 않으면 subset이 없는것이된다. 그리고 따로 약수총합을 구해서 제일 마지

막에 if문을써서 weird인지 아닌지 검사한다. 끝~

 

 

package com.tutorial;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class WEIRD {
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System. in));
        int cnt = Integer.parseInt(br.readLine());
        while (cnt -- > 0) {
            int a = Integer.parseInt(br.readLine());
            int sum = 0,
            sum1 = 0;
            boolean isNosubset = true;
            for (int i = a / 2; i > 0; i --) {
                if (isNosubset && a % i == 0) {
                    sum += i;
                    sum1 += i;
                    if (sum1 > a) {
                        sum1 -= i;
                    } else if (sum1 == a) {
                        isNosubset = false;
                        break;
                    }
                }
            }
            if (sum > a && isNosubset) 
                System.out.println("weird");
             else 
                System.out.println("not weird");
            
        }
    }
}