사용자 도구

사이트 도구


ps:problems:boj:2775

부녀회장이 될테야

ps
링크acmicpc.net/…
출처BOJ
문제 번호2775
문제명부녀회장이 될테야
레벨브론즈 2
분류

이항계수

시간복잡도O(T+k+n)
인풋사이즈T<=?, k<=14, n<=14
사용한 언어Python
제출기록31312KB / 76ms
최고기록52ms
해결날짜2021/10/01

풀이

  • 점화식을 세워보자. f(a,b) = f(a,b-1) + f(a-1,b) 가 된다.
  • f(a,b) = C(a+b,b+1) 라 하면, C(a+b,b+1) = C(a+b-1,b) + C(a+b-1,b+1)
  • n=a+b, k=b+1 이라 하면 C(n,k) =C(n-1,k) +C(n-1,k-1) 이라서 이항계수의 점화식이 된다
  • 따라서 C(a+b,b+1)를 구하면 된다.
  • C(a+b,b+1) 을 계산하는 것은 O(a+b) 이므로, T개의 테스트를 매번 이렇게 구하면 O(T(a+b))가 된다. 하지만 이항계수를 여러번 구할때는 미리 팩토리얼 값을 다 계산해 놓으면 각 쿼리에 대해 O(1)에 계산할 수 있고 이렇게 하면 총 시간복잡도 O(T+a+b)에도 해결 가능하다.
    • 숫자 범위가 작아서 실제 구현은 그냥 매번 이항계수를 구하는 O(T(a+b))으로 구현했다.

코드

"""Solution code for "BOJ 2775. 부녀회장이 될테야".

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

import math


def main():
    T = int(input())
    for _ in range(T):
        k = int(input())
        n = int(input())
        print(math.comb(k + n, k + 1))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U V I Y Y
 
ps/problems/boj/2775.txt · 마지막으로 수정됨: 2021/10/02 12:28 저자 teferi