사용자 도구

사이트 도구


ps:problems:boj:2575

수열

ps
링크acmicpc.net/…
출처BOJ
문제 번호2575
문제명수열
레벨골드 4
분류

그리디

시간복잡도O(sqrt(n))
인풋사이즈n<=1,000,000
사용한 언어Python 3.11
제출기록31256KB / 44ms
최고기록44ms
해결날짜2023/08/28

풀이

  • 끔찍한 수열 과 거의 동일한 문제.
  • 끔찍한 수열 에서는 n의 최대/최솟값, m의 최대/최솟값을 모두 구했었는데, 여기에서는 n의 최댓값과 m의 최솟값만을 출력해야 한다는 것만 다르다. 풀이는 동일해서 생략

코드

"""Solution code for "BOJ 2575. 수열".

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

Tags: [greedy]
"""


from teflib import numtheory


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

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

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

    print(n, m)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
J G K J Z
 
ps/problems/boj/2575.txt · 마지막으로 수정됨: 2023/08/28 08:53 저자 teferi