[C/C++] 프로젝트 오일러 #15 격자 경로의 수 구하기(조합)

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

 

이 문제는 격자(grid)를 기반으로 한 경로 계산 문제입니다. 다음은 문제의 배경과 요구사항입니다:

문제 설명:
2차원 격자가 주어졌을 때, 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 이동하는 경로의 수를 계산합니다. 이때 이동은 오직 오른쪽 또는 아래쪽 방향으로만 가능합니다. 격자의 크기는  \(n \times n\) 으로 주어지며, 경로의 조합 수를 계산하는 것이 목표입니다.

문제의 요구사항:
•  \(n \times n\)  크기의 격자에서 가능한 모든 경로의 수를 구하시오.
• 경로의 수는 조합 수식을 사용하여 계산됩니다. 수학적으로,  C(2n, n) 로 표현할 수 있습니다. 여기서  \(C(2n, n) = \frac{(2n)!}{n! \times n!}\) 입니다.
• 숫자가 커질 수 있으므로 정밀도 높은 계산이 요구됩니다.

격자 경로

 

예를 들면 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} \]

 

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

 

grid paths

 

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

//------------------------------------------------
//    Project Euler #15 - Counting fractions
//        - by Aubrey Choi
//        - created at 2014-12-31
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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);
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}