"0727 nCr table print"의 두 판 사이의 차이

2017년 7월 27일 (목) 11:21 기준 최신판

더 정확하게는 nCr table’s row print이다.

$\dbinom{n}{0} \cdots \dbinom{n}{n}$을 $10^9$로 나눈 나머지들을 모두 출력.

$ n < 1000 $ 이라는 조건이 있어서 그냥 파스칼의 삼각형을 모두 저장하는 식으로 금방 풀긴 했는데, discussion보고 또 머릿속에 번쩍.

점화식을 이용하면 된다. 위키에도 나와 있듯이, $${\binom {n}{k}}={\frac {n+1-k}{k}}{\binom {n}{k-1}}$$

뭐… 이제 더 나아지거나 그러지는 않겠지 남은 여생에 말이다. ㅎㅎㅎ

@@ 3번째 줄: / 3번째 줄: @@
 [https://www.hackerrank.com/challenges/ncr-table 원래 문제]
-\(\dbinom{n}{0} \cdots \dbinom{n}{n}\)을 모두 출력하되 값들은 모두 \(10^9\)으로 나눈 나머지.
+\(\dbinom{n}{0} \cdots \dbinom{n}{n}\)을 \(10^9\)로 나눈 나머지들을 모두 출력.
 \( n < 1000 \) 이라는 조건이 있어서 그냥 파스칼의 삼각형을 모두 저장하는 식으로 금방 풀긴 했는데, discussion보고 또 머릿속에 번쩍.