프로젝트 오일러 #15 격자 경로의 수 구하기

사실 이번 문제는 상당히 쉬운 편이라서 그다지 설명이 필요할 것도 없을 듯 합니다. 다른 프로그래머도 저랑 비슷한 접근을 했고요.  2014년 년 마지막 날을 이렇게 보내네요.

 

격자 경로

 

예를 들면 2x2 격자에서 오른쪽과 아래로만 갈 수 있는 경로의 수는, 오른쪽 이동을 R, 아래 이동을 D라 표현하면 다음과 같습니다.

RRDD

RDRD

RDDR

DRRD

DRDR

DDRR

 

위와 같이 총 6가지의 경우가 나옵니다.  이 중에 R만을 가지고 따진다면, 4개의 칸 중에 2개의 R을 배치하는 방법의 수입니다.

 

프로젝트 오일러의 문제 링크입니다.

https://projecteuler.net/problem=15

Problem 15 - Project Euler

 

결국 우리가 구해야 할 것은, \( _{40}C_{20} \)을 구하는 것입니다. 이 숫자는 굳이 프로그램을 구하지 않더라도 계산할 수 있습니다. 프로그램을 이용한다면, 32비트 정도로는 힘듭니다. 왜냐하면 두자리수를 20번정도 곱하고, 그보다 적은 수를 20번 나누는 문제이니, 대충 10자리 이상이 나올 듯 합니다. 실제로는 12자리수가 나옵니다.  단순 팩토리얼로 계산을 한다면, 32비트가 아니라 64비트 자료형인 long long을 써도 오버플로우가 생깁니다.  조합을 계산하는 여러가지 기법이 있지만, 여기서는 곱하면서 나누는 방식을 썼습니다.  n부터 n-k 까지의 곱에는 반드시 1부터 k+1까지의 인수가 존재합니다.  그것을 이용해서 나눗셈을 하는 것이죠.  그러면 정수를 유지하면서 조합식을 계산할 수 있습니다.

 

\[ \prod_{k=1}^{r} (n-k-1)/k \]

 

이 방법 말고도 파스칼의 삼각형 원리를 이용해서 계산할 수도 있습니다.

 

\[ _nC_r = ~_{n-1}C_r + ~_{n-1}C_{r-1} \]

 

그래보았자 원래의 조합의 수가 큰 경우는 모두 도로 아미타불입니다.  때로 나머지 연산이 주어질 때가 있고, 소수 나머지 연산이 주어질 때가 있습니다.  그 때에는 그에 맞는 알고리즘을 선택하면 됩니다.

 

다음 프로그램은 40개중에 20개를 선택하는 조합을 구하는 프로그램입니다.

//----------------------------------------------------------------------------------------
//  Project Euler #15 - Counting fractions
//    - by Aubrey Choi
//    - created at 2014-12-31
//----------------------------------------------------------------------------------------

void solve1()
{
  int n=40, r=1;
  long long c = 1;

  for(;r<=20;n--,r++) { c *= n; c /= r; }
  printf("Ans = %lld\n", c);
}