[BOJ][Python]1291 풀이

https://www.acmicpc.net/problem/1291

1291번: 이면수와 임현수

n = int(input())
ans = []

def factorization(num, prime_factors):
    if num == 1:
        return prime_factors
    for i in range(2, num+1):
        if num % i == 0:
            factorization(num//i, prime_factors)
            prime_factors.append(i)
            return prime_factors

def one(n):
    if n == 4 or n >= 6:
        s = sum([int(i) for i in str(n)])
        if s % 2 == 1:
            return True
        else:
            return False
    else:
        return False
        
def two(n):
    if n == 2 or n == 4:
        return True
    else:
        prime_factors = factorization(n, [])
        prime_factors = set(prime_factors)
        if len(prime_factors) != 0 and len(prime_factors) % 2 == 0:
            return True
        else:
            return False
        
ans.append(one(n))
ans.append(two(n))
if ans[0] == True:
    if ans[1] == True:
        print(4)
    else:
        print(1)
else:
    if ans[1] == True:
        print(2)
    else:
        print(3)

개인적으로 크게 마음에 드는 문제는 아니었습니다. 쓸데없는 사설이 길어서 문제의 핵심을 찾는데에 시간을 좀 낭비했거든요. 문제 자체는 그다지 어렵진 않습니다만 조건을 대충 보는 부분에 주의하시면 좋을 것 같습니다. 제가 그것 때문에 계속 틀렸으니까요. 해당 사항도 소개해보도록 하겠습니다.

 

이 문제의 핵심은 이면수의 조건이 무엇이고, 임현수의 조건이 무엇인지 파악하는 문제입니다. 실제로 이 세상에 존재하는 분류 조건은 아니고 그냥 이 문제에만 있는 거니까 별로 중요하진 않구요. 아무튼 이면수는 2, 3, 4의 합으로 만들 수 있는 숫자들 중 자릿수의 합이 홀수가 되는 숫자입니다. 여기서 중요한 부분은 2, 3, 4의 합으로 만들어지는 숫자인데요. 보통은 이렇게 무슨 무슨 숫자의 합으로 만들어진다~ 라고 하면 해당 숫자 자체도 포함이 되는 경우가 많습니다. 지금 같은 경우는 2, 3, 4도 포함이 되어야 한다는 얘기죠. 근데 이 문제는 아닙니다. 정말 2, 3, 4를 더해서만 만들어야 합니다. 사실 이게 엄밀하게 말해서 당연하긴 합니다. 2, 3, 4도 합에 포함이 된다는 말은 2 + 0이라는 얘기니까 조건과 맞지 않죠. 이 부분은 아마 제가 다른 경험 때문에 넘겨짚으면서 생긴 저의 실수입니다. 이 부분 덕분에 몇 십 번을 제출하고 다른 분들 코드는 어떤지 확인하고 다른 분 코드는 통과되는지 넣어보기도 하고 시간을 엄청 쏟았습니다.

 

임현수는 2 또는 4 이거나 합성수이면서 소인수의 개수가 짝수인 수입니다. 소인수분해 알고리즘을 짜라는 얘기죠. 입력의 범위가 2700이 최대이므로 그냥 반복문으로 짜도 됩니다. 저는 바로 떠오른게 재귀라서 재귀로 짰는데 while 반복문으로 짠 분들이 훨씬 많더라구요. 이 부분은 알아서 편한대로 짜면 될 것 같습니다.

 

뭐랄까 문제가 어렵지 않은데도 불구하고 이렇게 마음대로 생각하는 것 때문에 실수하는 일이 종종 있는 것 같습니다. 제 버릇 개 못준다고, 이런 실수를 자주하는 걸 알아서 정말 조심조심하는데 몇년에 한 번은 꼭 이런 일이 있는 거 같네요.