목록포함 배제의 원리 (1)

dh_0e

[PS] N포커 / C++ (백준 16565번)

조합론의 포함 배제의 원리를 사용하여 포카드가 나올 경우의 수를 구하는 문제dp[N][K] = N장의 카드를 뽑을 때, K개의 포카드 세트가 나올 수 있는 경우의 수를 저장하는 형식으로 1~N까지 차례로 구하며 dp로 풀 수 있을 것 같아서 5시간 동안 점화식을 찾았다... 결론적으로 이 전의 경우의 수는 관계 XN개의 카드를 뽑을 때, K개의 포카드 세트가 나왔다고 고정한 뒤, 나올 수 있는 경우의 수를 구한다.식: $cmp = {_{13}C_K} + {_{(52 - k \times 4)}C_{(N - K \times 4)}}$K를 1~N/4까지 구해준 다음, 포함 배제의 원리에 의해서 홀수번째는 더해주고, 짝수번째는 빼주면 N개의 카드를 뽑을 때 포카드가 나올 경우의 수를 구할 수 있다. ex) N이..
알고리즘/Baekjoon 2025. 3. 10. 11:39
이전 Prev 1 Next 다음