[Project Euler #15][C++] 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

문제15 : 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

문제

아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).

그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?

문제 해결 방법

• 격자에서 최단 경로의 수 를 찾는 문제이다.
• 규칙성을 찾아 문제를 해결하였다.
  • 배열 ary[20][20]에서 ary[n][n] = ary[n - 1][n] + ary[n][n - 1]이다.
• for 문을 사용하여 ary[x][0]과 ary[0][x]의 값을 모두 1로 설정하였다.
• 그리고 또 다른 for 문을 사용하여 찾은 규칙성을 바탕으로 배열에 값을 채워서 최종적으로 ary[SIZE][SIZE]에 있는 값이 출력되도록 하였다.

5 x 5 격자에서의 최단 경로의 수

0           1             1            1               1                1
1           2(1+1)      3            4               5                6
1           3             6(3+3)    10             15               21
1           4            10          20(10+10)   35               56
1           5            15          35             70(35+35)    126
1           6            21          56           126              252(126+126)

소스 코드

.

          0           1           1           1           1           1           1           1           1           1           1           1           1           1           1           1           1           1           1           1            1 
          1           2           3           4           5           6           7           8           9          10          11          12          13          14          15          16          17          18          19          20           21 
          1           3           6          10          15          21          28          36          45          55          66          78          91         105         120         136         153         171         190         210          231
          1           4          10          20          35          56          84         120         165         220         286         364         455         560         680         816         969        1140        1330        1540         1771
          1           5          15          35          70         126         210         330         495         715        1001        1365        1820        2380        3060        3876        4845        5985        7315        8855        10626
          1           6          21          56         126         252         462         792        1287        2002        3003        4368        6188        8568       11628       15504       20349       26334       33649       42504        53130
          1           7          28          84         210         462         924        1716        3003        5005        8008       12376       18564       27132       38760       54264       74613      100947      134596      177100       230230
          1           8          36         120         330         792        1716        3432        6435       11440       19448       31824       50388       77520      116280      170544      245157      346104      480700      657800       888030
          1           9          45         165         495        1287        3003        6435       12870       24310       43758       75582      125970      203490      319770      490314      735471     1081575     1562275     2220075      3108105
          1          10          55         220         715        2002        5005       11440       24310       48620       92378      167960      293930      497420      817190     1307504     2042975     3124550     4686825     6906900     10015005
          1          11          66         286        1001        3003        8008       19448       43758       92378      184756      352716      646646     1144066     1961256     3268760     5311735     8436285    13123110    20030010     30045015
          1          12          78         364        1365        4368       12376       31824       75582      167960      352716      705432     1352078     2496144     4457400     7726160    13037895    21474180    34597290    54627300     84672315
          1          13          91         455        1820        6188       18564       50388      125970      293930      646646     1352078     2704156     5200300     9657700    17383860    30421755    51895935    86493225   141120525    225792840
          1          14         105         560        2380        8568       27132       77520      203490      497420     1144066     2496144     5200300    10400600    20058300    37442160    67863915   119759850   206253075   347373600    573166440
          1          15         120         680        3060       11628       38760      116280      319770      817190     1961256     4457400     9657700    20058300    40116600    77558760   145422675   265182525   471435600   818809200   1391975640
          1          16         136         816        3876       15504       54264      170544      490314     1307504     3268760     7726160    17383860    37442160    77558760   155117520   300540195   565722720  1037158320  1855967520   3247943160
          1          17         153         969        4845       20349       74613      245157      735471     2042975     5311735    13037895    30421755    67863915   145422675   300540195   601080390  1166803110  2203961430  4059928950   7307872110
          1          18         171        1140        5985       26334      100947      346104     1081575     3124550     8436285    21474180    51895935   119759850   265182525   565722720  1166803110  2333606220  4537567650  8597496600  15905368710
          1          19         190        1330        7315       33649      134596      480700     1562275     4686825    13123110    34597290    86493225   206253075   471435600  1037158320  2203961430  4537567650  9075135300 17672631900  33578000610
          1          20         210        1540        8855       42504      177100      657800     2220075     6906900    20030010    54627300   141120525   347373600   818809200  1855967520  4059928950  8597496600 17672631900 35345263800  68923264410
          1          21         231        1771       10626       53130      230230      888030     3108105    10015005    30045015    84672315   225792840   573166440  1391975640  3247943160  7307872110 15905368710 33578000610 68923264410 137846528820

정답

137846528820

심화 공부

중복집합 순열(Permutations of Multisets)

중복집합 M의 각 원소의 개수가 $m_{1}, m_{2}, ..., m_{l}$이고 그 합이 $n$일 때 순열의 개수는 다음과 같다.

$$ {n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {(\sum _{i=1}^{l}{m_{i}})!}{\prod _{i=1}^{l}{m_{i}!}}} $$

예를 들어, 영단어 MISSISSIPPI의 모든 문자를 사용한 순열의 수는 다음과 같다.

$$ {\frac {11!}{1!\,4!\,4!\,2!}}=34650 $$

---

문제 출처 : https://euler.synap.co.kr/problem=15