[DP] 백준 10164 격자상의경로

tb배열은 왜만들었는지 모르겠다. 

몽롱해서 막 코딩했는데 되게 안됐다. 

삽질하느라 디버깅한다고 che2를 매번 확인하면서 깨달은게 있다.

che2배열은 0,0쪽에 결과가 더해져서 return 한다는 것. 

#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

#include <limits.h>

#include <queue>

#include <stack>

#include <vector>

using namespace std;

typedef long long ll;

int dx[] = { 0,1 };

int dy[] = { 1,0 };

//int tb1[100001];

ll tb2[20][20];

//int che[100001];

ll che2[20][20];

//int sum[1001];

int n, m;

//int min3(int a,int b,int c){

//     a = (a < b ? a : b);

//     return (a < c ? a : c);

//}

int aaa, bbb;

ll go(int s, int e, int fx, int fy) {

       if (che2[s][e] != -1) {

              return che2[s][e];

       }

       if (s == fx && e == fy) {

              return che2[s][e] = 1;

       }

       che2[s][e] = 0;

       ll& ret = che2[s][e];

       for (int k = 0; k < 2; ++k) {

              int nx = dx[k] + s;

              int ny = dy[k] + e;

              if (aaa <= nx && nx <= fx && bbb <= ny && ny <= fy) {

                     ret += go(nx, ny, fx, fy);

              }

       }

       return ret;

}

int main(void)

{

       int n, m,k;

       cin >> n >> m >> k;

       int a, b;

       bool ans_is_easy = false;

       if (k == 0) {

              ans_is_easy = true;

       }

       for (int i = 1; i <= n; ++i) {

              for (int j = 1; j <= m; ++j) {

                     tb2[i][j] = (i - 1)*m + j;

                     if ((i-1)*m+j == k && ans_is_easy == false) {

                           a = i, b = j;

                     }

              }

       }

       

       //cout << "a b " << a << ' ' << b << endl;

       aaa = 1;

       bbb = 1;

       memset(che2, -1, sizeof(che2));

       ll kk;

       if (!ans_is_easy) {

              kk = go(1, 1, a, b);

       }

       /*for (int i = 1; i <= n; ++i) {

              for (int j = 1; j <= m; ++j) {

                     cout << che2[i][j] << ' ';

              }

              cout << endl;

       }*/

       memset(che2, -1, sizeof(che2));

       ll kkk;

       if (ans_is_easy) {

              cout << go(1, 1, n, m);

              return 0;

       }

       else {

              aaa = a;

              bbb = b;

              kkk = go(a, b, n, m);

       }

       //for (int i = 1; i <= n; ++i) {

       //     for (int j = 1; j <= m; ++j) {

       //            cout << che2[i][j] << ' ';

       //     }

       //     cout << endl;

       //}

       cout << kk * kkk;

       

       return 0;

}