nCr 값을 여러 번 계산해야 한다고 가정합니다. 우리는 이것을 매우 효율적인 방법으로 해결할 수 있습니다. nCr의 더 낮은 값을 저장하면 더 높은 값을 쉽게 찾을 수 있습니다. 따라서 n이 있으면 nC0에서 nCn까지의 목록을 찾아야 합니다. 응답이 너무 크면 해당 모듈로 10^9를 반환합니다.
따라서 입력이 n =6과 같으면 출력은 [1, 6, 15, 20, 15, 6, 1]이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- items :=단일 요소가 1인 목록
- 1~n 범위의 r에 대해 다음을 수행합니다.
- 항목의 끝에 (항목의 마지막 요소 * (n-r+1) /r)의 바닥 삽입
- items[n-2] :=items[n-2] mod 10^9 여기서 n은 항목의 크기입니다.
- 반품
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n): items = [1] for r in range(1,n+1): items.append(items[-1]*(n-r+1)//r) items[-2] %= 10**9 return items n = 6 print(solve(n))
입력
6
출력
[1, 6, 15, 20, 15, 6, 1]