파스칼 삼각형

[1. 개요]

파스칼의 삼각형은 이항계수, 조합(Combination) 과 본질적으로 그 의미가 같다.

 

특히, 경우의 수를 계산해야 할 때 그 수식 계산을 직접 구현해야하는 경우가 번거로울 수 있다.

• 특히, mod 연산을 해야하는 경우라면 난이도가 더 올라가게 됨.
• 페르마 소정리를 적용해야 하기에..

그러나, 이러한 계산을 파스칼의 삼각형을 구하듯 계산하면 그 난이도가 조금 더 쉬워진다.

단순 덧셈 연산만 존재하기에  mod 연산의 분배법칙이 조금 더 수월하게 된다.

 

따라서, 파스칼 삼각형을 이용하여 이항계수를 계산하도록 하는 편이 조금 더 나을지도 모르겠다.

• (n, k) 에서 n 이 너무 커지면 적용하기 어려울지도,
• n 에 해당하는 배열을 할당 할 수 없음. (이 경우는 직접 계산하는 방식으로 접근해야 함.)

예제 (https://www.acmicpc.net/problem/16395)

 

구현을 위한 메모리를 할당을 위해서

1. n*n 의 2차원 배열을 할당하여 처리 할 수 도 있지만,
2. 2*n 의 2차원 배열을 할당하여 처리 할 수 있음. (바로 위 행의 결과만 필요하기에...)

---

[2. 코드]

---

[2.1 코드]