알고스팟 weird numbers (weird) 문제 파이썬으로 풀기

숫자를 입력받고, 그 숫자가 weird 인지 아닌지 판별하는 문제이다.

어떤 수가 weird이라면, 그 수 자신을 제외한 약수의 합이 자신보다 커야하고, 수 자신을 제외한 약수 집합의 모든 부분합이 그 숫자가 되면 안된다.

이 문제는 전에도 시도해 보았지만, 시간을 넘기거나 오답이 계속 나와서 다른 코드를 좀 참조해서 풀었다.

우선 첫번째 조건인 약수집합의 합을 빠르게 구하기 위해서

출처: https://algospot.com/forum/read/470/

이 코드를 이용했다. i^2를 이용해 시간을 줄이면서도, 제곱수를 한번만 추가하게 하는 코드가 좋아보여서 썼다.

두번째 조건을 위해선 아래의 코드를 이용했다.

출처: https://baboc.tistory.com/270

약수집합과 구하는 수를 점점 줄여나가는 방법이다. 문제를 간소화 하는 방식이 좋아 보여서 썼다.

그렇게 가져온 코드를 파이썬식으로 변형했다.

#weird
import sys
 
 
def solve(leng, summ, target):  # 부분합 중 수 자체와 같은 것이 있는지 검사
    if summ == target:  # leng=약수집합의 길이, summ=약수의 부분합, target=검사하는 수 자체
        return True  
    if summ < target or target < 0:
        return False
    if solve(leng-1, summ-divsors[leng-1], target-divsors[leng-1]):
        return True
    return solve(leng-1, summ-divsors[leng-1], target)
 
 
case = int(sys.stdin.readline())
for i in range(case):
    n = int(sys.stdin.readline())
    divsors = []  # 약수 집합
    j = 1
    while 1:
        if j*j > n:  # 약수를 다 구했으므로
            break
        if n % j == 0:  # 약수이면 약수집합에 넣는다
            divsors.append(j)
            if n / j != j:  # 제곱수는 한번만 넣어야 함
                divsors.append(int(n/j))  # int 없이 쓰면 소수로 나옴
        j += 1
    divsors.sort()
    del divsors[-1]  # 약수집합에서 수 자신을 제외
    sums = sum(divsors)  # 약수집합 전체의 합
    if sums > n and solve(len(divsors), sums, n) == 0:  # 조건이 맞다면 weird 출력
        print("weird") 
    else:
        print("not weird")

예를 들어, 6이 weird인지 아닌지를 보자. 6의 약수집합은 [1,2,3]이다. solve 함수를 부르면 solve[3,6,6]이 호출된다.

처음 불러질 때 summ=6이고 target=6이고, target=summ 이므로 True를 리턴한다.

약수집합의 합이 본 수보다 크지 않고 solve함수의 리턴값이 0이 아니므로 6은 not weird이다.

 

느낀점: 

1. solve 함수의 원본 코드가 부분합이 n이 되면 true를 출력하는 건데, 처음엔 그걸 바꾸어 부분합이 n이 안되게 하고 싶었다.(if sums>n and solve(len(divisors), sums, n)): print("weird")이런식으로) 그러나 귀찮아서 그냥 solve()==0이면 weird를 출력하게 썼다. 나중에 바꿔보면 좋은 경험이 될수도..?

2. 보통 약수를 구할때 for(int i = 1; i < n; ++i) if(n % i == 0) divisors.push_back(i); 이런식으로 하나씩 수를 증가시키는 방법을 쓰지만, i^2<=n일때까지 루프를 돌리는 방식은 처음보았다. 매우 좋은 방법인거같다.

3. 파이썬은 정말 좋은 내장함수가 많아서 마음에 든다. sum함수도 있고, len도 있고... 나같은 코알못에게 딱 맞는, 쉬운 언어이다.