[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$$

 

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

 

$${}_n{C}_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;
}