끔찍한 수열

• 합이 일정하고, 곱을 최대화 하는 분할을 먼저 생각해보자. 몇몇 수에 대해서 생각해보면, 3으로 가장 많이 쪼개는 것이 최적이라는 것을 알수 있다. 케이스를 나눠서 정확히 분류해보면..
  • 합이 3의 배수이면, (3+3+3+…+3) 으로 나누는 것이 최적이다
  • 합이 3k+1 이면, (3+3+3+…+3+4) 또는 (3+3+3+…+3+2+2) 로 나누는 것이 최적이다
    • 이때에만 수열의 길이의 최댓값과 최솟값이 달라진다
  • 합이 3k+2 이면, (3+3+3+…+3+2) 로 나누는 것이 최적이다
• 곱이 일정하고, 합을 최소화 하는 분할도 간단하게 해결된다. 최대한 많은 수로 쪼개는 것이 합을 최소화하게 된다. 한가지 예외는 4의 경우로, 2*2로 쪼개는 것과 4를 그냥 두는 것이 합이 동일하다.
  • 최적 수열의 길이의 최댓값은 소인수분해에 포함된 수의 갯수를 모두 더해서 쉽게 구할수 있다. 소인수분해 결과가 2를 2개 이상 포함하고 있을때에는 그것들을 4로 바꾸어주면, 최적 수열의 길이의 최솟값을 구할수 있다.
• 걸리는 시간은 소인수분해의 시간복잡도에 바운드된다. O(sqrt(n)).

"""Solution code for "BOJ 1877. 끔찍한 수열".

- Problem link: https://www.acmicpc.net/problem/1877
- Solution link: http://www.teferi.net/ps/problems/boj/1877

Tags: [greedy]
"""


from teflib import numtheory


def main():
    M = int(input())

    if M <= 3:
        n_max = n_min = 1
    else:
        q, r = divmod(M, 3)
        n_min = q + (0 if r <= 1 else 1)
        n_max = q + (0 if r == 0 else 1)

    if M == 1:
        m_max = m_min = 1
    else:
        factorization = numtheory.prime_factorization_small(M)
        m_max = sum(factorization.values())
        m_min = m_max - factorization.get(2, 0) // 2

    print(n_max, n_min, m_max, m_min)


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_factorization_small