사용자 도구

사이트 도구


ps:problems:boj:16565

N포커

ps
링크acmicpc.net/…
출처BOJ
문제 번호16565
문제명N포커
레벨골드 1
분류

포함배제의 원리

시간복잡도O(n)
인풋사이즈n<=52
사용한 언어Python
제출기록31312KB / 68ms
최고기록60ms
해결날짜2021/10/18

풀이

  • N장중에서 포카드가 1종류 이상 포함된 경우의 수를 구하면 된다.
  • 포함배제의 원리를 이용하면, 아래처럼 계산하면 된다..
    • {1포카드가 포함된 경우}, … , {13포카드가 포함된 경우} 를 더하고
    • {1포카드와 2포카드가 포함된 경우}, {1포카드와 3포카드가 포함된 경우}, … , {12포카드와 13 포카드가 포함된경우} 를 빼고
    • {1,2,3 포카드가 포함된 경우}, {1,2,4 포카드가 포함된 경우}, … , {11,12,13포카드가 포함된경우} 를 더하고
  • X포카드가 포함된 경우의 수는. 4장을 X로 채우고, 나머지 N-4장은 52-4장중에서 고르면 되니까 C(52-4, N-4). X의 가짓수는 13개
  • X,Y포카드가 포함된 경우의 수는. 8장을 X,Y로 채우고, 나머지 N-4장은 52-4장중에서 고르면 되니까 C(52-8, N-8). (X,Y)의 가짓수는 C(13,2)개
  • 이제 식을 정리하면 C(13,1)*C(52-4,N-4) - C(13,2)*C(52-8,N-8) + C(13,3)*C(52-12,N-12) - …. = sigma{(-1)^(i-1) * C(13,i)*C(52-i*4,N-i*4)} 을 계산해주면 된다. N-4*i 가 양수인 동안만 계산하면 된다
  • 시간복잡도는 항 한개를 계산하는데는 전체 카드 장수에 비례하는 시간이 걸리는데 전체 카드 장수는 52로 고정되어있으므로 그냥 상수취급해도 된다. 항이 N/4 개이므로 그냥 전체 복잡도는 O(N)

코드

"""Solution code for "BOJ 16565. N포커".

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

Tags: [Inclusion-Exclusion Principle]
"""

import math

MOD = 10007


def main():
    N = int(input())
    answer = 0
    for i in range(1, N // 4 + 1):
        count = math.comb(13, i) * math.comb(52 - 4 * i, N - 4 * i)
        answer += count if i % 2 else -count
    print(answer % MOD)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
S P Y F F
 
ps/problems/boj/16565.txt · 마지막으로 수정됨: 2021/10/20 14:51 저자 teferi