백준 1291: 이면수와 임현수 (Python)

문제

중급반을 담당하는 배성경 조교는 이 세계에 있는 모든 자연수들을 분석했다.

 

(중간 생략...)

 

숫자 4는 위대한 숫자 1과 시작의 숫자 3의 합으로 “완벽하다”라는 의미를 갖는 완벽한 숫자이다. 그와 동시에, 이 완벽한 숫자와 태초의 숫자들(2와 3)의 합으로 표현되는 숫자들, 즉 6, 7, 8, 9, 10 ... 들 역시 포함해서 “처음부터 완벽했던, 태초부터 존재했던”이라는 의미인 “완전[피-얼프 에크트(perfect)]” 혹은 “신이 태초부터 완성시켜져 있었던 계급[어비스 오엘 우테(absolute)]”이라고 부른다.

 

(중간 생략...)

 

숫자 2는 최초의 짝수로 “사람 둘이 모이면 스타 1:1을 할 수 있다.”라는 의미로 “starcraft number”라고 불렀다.

 

(중간 생략...)

 

숫자 4는 4명이 모이면 닭싸움을 한다는 숫자로, 그래서 chicken number, 혹은 꼬꼬댁수 라고 불린다.

 

어떤 숫자가 “이면수”이기 위해서는 다음과 같은 조건을 만족해야 한다. 메갈루젼 문명의 자연수 분류방식에 있던 “신이 태초부터 완성시켜져 있었던 계급[어비스 오엘 우테(absolute)]”에 속해 있어야 하고, 각 자릿수의 합이 홀수여야 한다.

 

또한 어떤 숫자가 "임현수"이기 위해서는 그 숫자가 자체가 월드 문명의 chicken number 혹은 starcraft number이거나 합성수이면서 소인수 분해를 했을 때 소인수의 종류의 개수가 짝수개 이어야 한다.

 

조교 배성경은 자신의 이름을 역사에 남기기 위해서 이면수도, 임현수도 아닌 숫자를 “성경수”라고 정의했다.

 

어떤 숫자 N이 주어지면, 그 숫자를 분석한 결과를 출력하도록 한다.

 

만약 그 숫자가 이면수라면 “1”라고 출력하고, 그 숫자가 임현수라면 “2”라고 출력한다. 주어진 수가 이면수도 임현수도 아닐 수 있는데 그럴 경우에는 배성경 조교가 정의한 대로 “3”를 출력한다. 혹은, 그 숫자가 이면수이면서 임현수이면 “4”를 출력하도록 한다.

 

해설

(무슨 약을 하셨길래 이런 문제를 만드셨습니까)

해석이 비문학급으로 난해할 뿐 요점만 정리하면 문제가 요구하는 것은 그리 어렵지 않다.

 

이 문제는 주어진 N에 대해 다음 조건에 따라 분석하여 결과를 출력하는 문제이다.

• 조건 1: 주어진 숫자가 "이면수"인지 확인한다.
  • 이면수는 자릿수의 합이 홀수이고, 2와 3의 합으로 표현되는 수이다.
• 조건 2: 주어진 숫자가 "임현수"인지 확인한다.
  • 임현수는 2 또는 4 중 하나이거나, 합성수이면서 소인수 분해했을 때 소인수의 종류의 개수가 짝수인 수이다.
• 조건 3: 주어진 숫자가 이면수이면서 임현수인지 확인한다.
• 조건 4: 조건 1, 2, 3 중 어느 조건에도 해당하지 않는 경우 "성경수"로 분류한다.

그렇게 분석한 결과를 출력하는 문제로 이해하면 된다.

 

다음은 문제를 구현한 코드다.

코드

def generatePrimeNumber(size):  # 소수 생성기
    DP = [0] * size
    prime = []
    for i in range(2, size, 1):
        if not DP[i]:
            prime.append(i)
            for j in range(i*2, size, i):
                DP[j] = 1
    return prime


def isDigitOdd(n):  # 각 자릿수가 홀수인가?
    sum_value = 0
    for ch in str(n):
        sum_value += int(ch)
    if sum_value % 2 == 0:
        return False
    else:
        return True


def getPrimeFactor(n, primes):  # 소인수 분해
    factors = []
    for prime in primes:
        if n < prime:
            break

        count = 0
        while n % prime == 0:
            n //= prime
            count += 1
        if count > 0:
            factors.append([prime, count])
    return factors


def isCompositeNumber(n):  # 합성수 판별
    if 1 < n and n not in primes:
        return True
    return False


def isImyeonsu(n):  # 이면수 판별
    if 6 <= N and isDigitOdd(N):
        return True
    return False


def isImHyunsoo(n):  # 임현수 판별
    if N == 2 or N == 4 or (isCompositeNumber(N) and len(getPrimeFactor(N, primes)) % 2 == 0):
        return True
    return False


N = int(input())
primes = generatePrimeNumber(2700)
# 4. 이면수 and 임현수
if isImyeonsu(N) and isImHyunsoo(N):
    print(4)
# 1. 이면수
elif isImyeonsu(N):
    print(1)
# 2. 임현수
elif isImHyunsoo(N):
    print(2)
# 3. not 이면수 and not 임현수
elif not isImyeonsu(N) and not isImHyunsoo(N):
    print(3)