백준 10164 격자상의 경로(dynamic programming)

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

10164번: 격자상의 경로

이 문제는 내가 푼 버전 한 개와 다른 사람의 코드 버전 한 개를 가져왔다.

 

#include <iostream>

using namespace std;

int N, M, circledNum;
int dp[16][16];
int dp2[16][16];
void way()
{
    int via_X = (circledNum - 1) / M + 1; //반드시 거쳐야 하는 x지점
    int via_Y = (circledNum - 1) % M + 1; //반드시 거쳐야 하는 y지점
    if (circledNum == 0)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                dp[i][j] = max(1, dp[i - 1][j] + dp[i][j - 1]);
            }
        }
        cout << dp[N][M];
    }
    else
    {
        for (int i = 1; i <= via_X; i++)
        {
            for (int j = 1; j <= via_Y; j++)
            {
                dp[i][j] = max(1, dp[i - 1][j] + dp[i][j - 1]);
            }
        }
        for (int i = via_X; i <= N; i++)
        {
            for (int j = via_Y; j <= M; j++)
            {
                dp2[i][j] = max(1, dp2[i - 1][j] + dp2[i][j - 1]);
            }
        }
        cout << dp[via_X][via_Y] * dp2[N][M];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> circledNum;
    way();
}

 

가장 먼저 움직일 수 있는 방향이 아래와 오른쪽 뿐임으로 갈 수 있는 경우의 수를 구하는 점화식은 

dp[i][j] = dp[i-1][j] + dp[i][j-1]

라고 할 수 있다.

 

하지만, 이 문제에서는 중간에 거쳐야 하는 지점이 있을 수도 있다. 이 경우 최종 지점까지 가는 경우의 수는 분할을 통해 구할 수 있다.

 

예를 들어 3*5 행렬에서 반드시 지나야 하는 지점이 8이라면

 

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15

 

이런 테이블이 될 것 이다. 경우의 수를 구하기 위해서는 이분할을 진행해야 하는데

 

1	2	3
6	7	8

 

8	9	10
13	14	15

 

로 나누어야 한다. 1에서 시작해서 8까지 가는 경우의 수(3)와 8에서 시작해서 끝지점인 15까지 가는 경우의 수(3)를 곱해서 9라는 값이 나와야 하기 때문이다.

 

 

---

 

처음 알게 된 다른 방법이 있는데, 반드시 거쳐야 하는 지점(여기서는 8을 예로 들자면) 8의 우측 상단(4와 5), 8의 좌측 하단(11과 12)의 dp 테이블을 0으로 고정시키면 분할하지 않고도 거쳐서 가는 경우의 수를 구할 수 있게 된다.

 

#include <iostream>

using namespace std;

int N, M, circledNum;
int dp[16][16];
void way()
{
    int via_X = (circledNum - 1) / M + 1; //반드시 거쳐야 하는 x지점
    int via_Y = (circledNum - 1) % M + 1; //반드시 거쳐야 하는 y지점
    if (circledNum == 0)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                dp[i][j] = max(1, dp[i - 1][j] + dp[i][j - 1]);
            }
        }
        cout << dp[N][M];
    }
    else
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                if (i < via_X && j > via_Y)
                    dp[i][j] = 0;
                else if (i > via_X && j < via_Y)
                    dp[i][j] = 0;
                else
                {
                    dp[i][j] = max(1, dp[i - 1][j] + dp[i][j - 1]);
                }
            }
        }
        cout << dp[N][M];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> circledNum;
    way();
}

 아래 개념을 바탕으로 짠 코드가 훨씬 깔끔하다. 뭐 어떤 개념을 써도 상관없지만 혹시 모르니 두 개념을 기억해둬야겠다.