[10164번] 격자상의 경로(Dynamic Programming, Mathematic)

문제 출처 :

 

https://www.acmicpc.net/problem/10164

알고리즘 분석 :

문제 해결에 필요한 사항

1. 하나의 거쳐야 하는 특정 경로를 지나가는 알고리즘

2. 1번을 이용하기 위한 Dynamic Programming

3. 위의 방식이 아닌 순열, 조합으로 수학적 접근

이 문제는 DP로 접근해도 되고, 고등학교 수학의 순열 조합인 수학적 접근을 하여도 된다.

수학적 접근을 어떻게 하였냐면

aaabb로 이루어진 순열의 모든 경우의 수를 구할 때 5! / (3! * 2!)으로 한다.

이처럼 이 코드에서도 이러한 방법을 이용하였는데

ex ) 15! / 3! * 2!을 하게되면 15!을 먼저하다보면 값이 너무 커져서 

      자료형에서 overflow가 일어 날 수 도 있다.

              따라서 15 / 3 / 2 * 14 / 2 * 13 * 12 * 11 ... 이런식으로 곱하기와 나누기를 동시에 계속 해주는 알고리즘을 제작하였다. 

코드가 다소 복잡할 수 도 있으니, 알고리즘을 어떻게 구성하였는지 확인만 하고 넘어가도 좋다.

소스 코드 : 

< 수학적 접근 > 

#include <stdio.h>
 
double result1 = 1;
double result2 = 1;
int n, m, k;
int xy = 0;
int lr = 0;
 
int main()
{
    int map[16][16];
 
 
    int right, down;
 
    int x, y;
    int i, j,t = 1;
    int tmpx, tmpy;
 
 
    scanf("%d %d %d", &n, &m, &k);
 
    // 특정 거쳐야 하는 경로가 없을 경우
    if (k == 0)
    {
        // 가로 세로 총 합을 구한다.
        xy = n - 1 + m - 1;
 
        /*
        ex ) 15! / 3! * 2!을 하게되면 15!을 먼저하다보면 값이 너무 커져서 
             자료형에서 overflow가 일어 날 수 도 있다.
             따라서 15 / 3 / 2 * 14 / 2 * 13 * 12 ... 이런식으로 곱하기와 나누기를 동시에 계속 해주는 알고리즘이다. 
        */
        
        while (xy > 1)
        {
            if (xy > 1)
            {
                result1 = result1 * xy;
 
                if (m - 1 > 1)
                {
                    result1 = result1 / (m - 1);
                    m--;
                }
 
                if (n - 1 > 1)
                {
                    result1 = result1 / (n - 1);
                    n--;
                }
 
                xy--;
            }
        }
        printf("%0.lf", result1);
 
        return 0;
    }
 
 
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            map[i][j] = t;
 
            if (map[i][j] == k)
            {
                y = i+1;
                x = j+1;
            }
 
            t++;
        }
    }
 
 
    xy = x - 1 + y - 1;
    tmpx = x;
    tmpy = y;
 
    while (xy > 1)
    {
        if(xy > 1)
        {
            result1 = result1 * xy;
 
            if (x - 1 > 1)
            {
                result1 = result1 / (x - 1);
                x--;
            }
 
            if (y - 1 > 1)
            {
                result1 = result1 / (y - 1);
                y--;
            }
 
            xy--;
        }        
    }
 
    right = m - tmpx;
    down = n - tmpy;
 
    lr = right + down;
 
    while (lr > 1)
    {
        if (lr > 1)
        {
            result2 = result2 * lr;
 
            if (right > 1)
            {
                result2 = result2 / (right);
                right--;
            }
 
            if (down > 1)
            {
                result2 = result2 / (down);
                down--;
            }
 
            lr--;
        }
    }
    
    printf("%0.lf", result1 * result2);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

<Dynamic Programming >

.

#include <stdio.h>
int table[16][16] = { 0, };
 
int main(void) {
    int N, M, K;
    int i, j;
    int x, y;
 
    scanf("%d %d %d", &N, &M, &K);
    x = ((K % M) == 0)?M:(K % M);
    y = ((K % M) == 0)?(K/M) :(K / M) + 1;
 
    table[1][1] = 1;
 
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= M; j++) {
            if (i == 1 && j == 1)
                continue;
 
            if (K !=0 &&((i < y && j > x) || (i > y && j < x))){
                table[i][j] = 0;
            }
            else {
                table[i][j] = table[i - 1][j] + table[i][j - 1];
            }
        }
    }
 
    printf("%d", table[N][M]);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>