파이썬으로 좋은 약수(Nice Divisors) 개수 최대화하기

문제 설명

소인수의 개수를 나타내는 값 pf가 주어질 때, 다음 조건을 만족하는 양의 정수 n을 만들어야 합니다.

조건 1: n의 소인수 개수(중복 허용)는 pf 이하이어야 합니다.
조건 2: n의 '좋은 약수(nice divisor)' 개수가 최대가 되어야 합니다. 여기서 좋은 약수란 n의 모든 소인수로 나누어떨어지는 약수를 의미합니다.

목표는 n의 좋은 약수 개수를 구하는 것이며, 결과가 너무 클 경우에는 10⁹ + 7로 나눈 나머지를 반환합니다.

예제로 이해하기

pf = 5인 경우를 생각해 보겠습니다. n = 200으로 두면 소인수는 [2, 2, 2, 5, 5]이고, 좋은 약수는 [10, 20, 40, 50, 100, 200]으로 총 6개입니다. 따라서 정답은 6이 됩니다.

핵심 아이디어: 정수 분할 문제로 환원

n을 n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ 형태로 표현하면, 지수의 합(a₁ + a₂ + … + aₖ)은 pf 이하이어야 합니다. 좋은 약수는 모든 소인수를 적어도 한 번씩 포함해야 하므로, 좋은 약수의 개수는 각 지수 aᵢ의 곱과 같습니다.

결국 이 문제는 '합이 pf가 되도록 양의 정수로 나눌 때 곱을 최대화'하는 고전적인 정수 분할(integer break) 문제와 동일합니다. 곱을 최대화하려면 가능한 한 많이 3으로 쪼개는 것이 가장 유리하며, 나눗셈의 나머지에 따라 세 가지 경우로 처리합니다.

알고리즘 단계

pf가 1이면 1을 그대로 반환합니다.
m := 10⁹ + 7 (모듈러 상수)
q := pf ÷ 3의 몫, r := pf ÷ 3의 나머지
r이 0이면 → 3^q mod m을 반환합니다.
r이 1이면 → (3^q−1 mod m) × 4 mod m을 반환합니다. 하나의 3과 남은 1을 합쳐 4로 만드는 편이 곱을 더 크게 만들기 때문입니다(3 × 1 < 2 × 2).
그 외(r이 2이면) → (3^q mod m) × 2 mod m을 반환합니다.

파이썬 구현 예제

아래 코드를 통해 더 잘 이해할 수 있습니다.

def solve(pf):
    if pf == 1:
        return 1
    m = 10**9 + 7
    q, r = divmod(pf, 3)
    if r == 0:
        return pow(3, q, m)
    elif r == 1:
        return pow(3, q - 1, m) * 4 % m
    else:
        return pow(3, q, m) * 2 % m

pf = 5
print(solve(pf))

입력 및 실행 결과

입력: 5
출력: 6

복잡도 분석

모듈러 거듭제곱(pow 함수)을 활용하므로 시간 복잡도는 O(log pf)이며, 추가 메모리 없이 O(1) 공간 복잡도로 해결할 수 있습니다.

마무리

이 문제는 정수 분할 원리만 이해하면 몇 줄의 코드로 해결할 수 있는 수학 기반 알고리즘 문제입니다. 3을 최대한 활용하고 나머지에 따라 보정하는 패턴은 코딩 테스트에서 자주 등장하니 꼭 익혀두시길 바랍니다.

파이썬으로 좋은 약수(Nice Divisors) 개수 최대화하기 – 정수 분할 알고리즘 풀이