[백준 16565번] N포커 (Python3)

import sys
input = sys.stdin.readline
mod = 10007

def cal(x,n):
  if n == 1:
    return x
  cal2 = cal(x,n//2)
  if n%2:
    return cal2*cal2*x
  return cal2*cal2

def div(x,y):
  return x*cal(y,mod-2)%mod

def combination(n,k):
  numor = 1
  denom = 1
  for i in range(k):
    numor = numor*(n-i)%mod
    denom = denom*(i+1)%mod
  return div(numor,denom)

def Ncard(N):
  result = 0
  for i in range(1,N//4+1):
    result += combination(52-i*4,N-i*4)*combination(13,i)*((-1)**(i-1))
    result %= mod
  return result

print(Ncard(int(input())))

 

특별히 어려운 문제는 아닌데, 그동안 배운 계산법을 동원해서 풀어봤다.

 

일단 경우의 수를 찾는 알고리즘은 다음과 같다.

1. N//4가 곧 N의 카드에 포카드 쌍이 몇개 들어갈 수 있는지이다.

2. 예를들어 포카드 쌍이 1개 들어갔다면, 4개를 뺀 나머지 (52-4=48)개에서 남은 카드를 뽑는 경우의 수를 combination 함수로 구하고, 포카드의 가짓수를 곱한다. (13개의 포카드 쌍 중 1개를 뽑는 가짓수)

3. 이때 겹치는 경우의 수가 존재하므로 교집합의 공식에 근거해서 포카드 2쌍을 넣는 경우의 수를 빼주고, 3쌍을 넣는 경우의 수를 더해주고, 4쌍을 넣는 경우의 수를 더해주고... 하는 식으로 가질 수 있는 포카드 쌍만큼을 더하고 빼고를 해서 총 경우의 수를 구한다.

 

이때 계산을 위해 사용한 알고리즘은 다음과 같다.

1. 분할정복을 통한 거듭제곱 알고리즘

2. 페르마의 소정리를 이용한 나눗셈

3. 이를 이용한 이항계수 출력 ([백준 11401번] 이항 계수 3 (Python3) (tistory.com) 참고)

 

 

다른 사람들 풀이를 보니 DP로 푼 사람도 있고, 전체 경우의 수에서 포카드를 하나도 안뽑는 경우의 수를 뺀 사람도 있고, 여러가지 풀이 방식이 있는 것 같았다. 

어쨌든 내 풀이 방식도 68ms 만에 통과한 걸 보니 나쁘지 않은 풀이인 듯하다.

 

오늘의 교훈) 페르마의 소정리는 유용하다