[백준 24419번 C++: 알고리즘 수업 - 행렬 경로 문제 2]

문제 링크

해당 문제는 (1,1) 에서 (n,n)까지 이동하는 모든 경로의 점수중에 가장 높은 점수를 구하는 행렬 코드의 실행횟수를 구하는 문제입니다. 

 

첫번째 방법은 (n,n)에서 부터 거꾸로 (1,1)까지 각 위치에서 왼쪽이나 위쪽에서의  최대 점수를 더해서 현재 위치의 최대 점수를 구하는 방식으로 모든 가능한 경로를 탐색해서 찾고 있습니다.

(1,1)에서 (n,n) 까지 가기 위해서는 가로로 n-1 칸, 세로로 n-1칸 이동해야 되므로 총 2n-2 칸을 이동해야 합니다. 이동 방향이 아래,오른쪽 두가지 밖에 없으므로 n-1개의 칸의 방향을 정하게 된다면 나머지 칸의 방향은 자동적으로 정해집니다.

 

그렇기 때문에 2n-2 중 n-1개를 선택하는 방법의 수가 (1,1)에서 (n,n)까지 가능한 모든 경로의 수가 됩니다. 

$$^{2n-2}C_{n-1} = \frac{(2n-2)!}{(n-1)!(n-1)!}$$

위의 식을 계산하기 쉽게 간단히 만들자면 위아래로 (n-1)을 제거할 수 있습니다.

$$^{2n}C_{n} = \frac{(2n)!}{(n)!(n)!}$$

 

위의 식을 계산하는 방법은 다양하게 구현하면 될것같습니다. 
항상 식을 좀 더 간편히 할수 없을까 해서 방법을 찾아보다가 페르마의 소정리를 찾게 되어서 해당 방법을 통해서 연산을 구현했습니다.

 

페르마의 소정리란

페르마의 소정리란 p가 소수이고, a가 p의 배수가 아닐 때, 아래의 식이 성립합니다.
$$a^{p-1} = 1 (mod\;p)$$

양변의 a로 나누게 되면, 아래의 식으로 역함수를 구할 수 있게 됩니다.

$$a^{p-2} = a^{-1} (mod\;p)$$

해당 식을 통해 나눗셈을 곱셈으로 표현할 수 있습니다.

 

해당 문제의 입력으로 크기 n과 각 칸의 값을 주는데 각 값은 실행횟수를 구하는데 있어서 필요없기 때문에 받기만 했습니다.

#include <iostream>
#include <vector>

#define MOD 1000000007

using namespace std;

long long modMul(long long a,long long b){
    return (a*b)%MOD;
}

long long modPow(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = modMul(result,base);
        }
        base = modPow(base,base);
        exp /= 2;
    }
    return result;
}

int main(){
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int num;
            cin >> num;
        }
    }

    long long ans = 1;

    long long div = 1;
    for(int i = 0; i < n; i++){
        ans = modMul(ans,2*n -i);
        ans = modMul(ans,modPow(i+1,MOD-2));
    }

    cout << ans << " " << n*n << "\n";
    return 0;
}