[C++] 백준 1010번 다리 놓기

 

다이나믹 프로그래밍 문제입니다.

 

왼쪽과 오른쪽에 서로 다리를 놓을때 교차하지 않는 한에서

최대로 놓을 수 있는 경우의 수를 구하는 문제입니다.

왼쪽이 항상 오른쪽보다 작거나 같습니다.

 

예를들어 

서쪽에 3, 동쪽에 5라는 숫자가 있으면

서쪽을 기준으로 시작합니다.

 

3부터 3-3, 3-4, 3-5의 경우의 수를 구합니다.

3-5는 3-5 = 1번

3-4는 3-4, 3-5 = 2번

3-3은 3-3, 3-4, 3-5 = 3번

 

다음 2는 2-2, 2-3, 2-4

2-4는 3-5의 경우의 수 = 1번

2-3은 3-4, 3-5의 경우의 수 = 3번

2-2는 3-3, 3-4, 3-5의 경우의 수 = 6번

 

마지막 1은 1-1, 1-2, 1-3

1-3은 2-4의 경우의 수 = 1번

1-2는 2-3, 2-2의 경우의 수 = 4번

1-1는 2-2, 2-3, 2-4의 경우의 수 = 10번

 

총 결과는 10이 됩니다.

 

코드로 구현하면

if (y == last) {
 	DP[x][y] = DP[x + 1][y + 1];
 	return DP[x][y];
}
DP[x][y] += func(x, y + 1, last) + DP[x + 1][y + 1];

다음과 같은 재귀함수로 풀었습니다.

 

#include <iostream>
using namespace std;

int DP[40][40];
int west, east;

void init()
{
   for (int i = 0; i < 40; ++i) {
      for (int j = 0; j < 40; ++j) {
         DP[i][j] = 0;
      }
   }
}

int func(int x, int y, int last)
{
   if (DP[x + 1][y + 1] != 0) {
      if (y == last) {
         DP[x][y] = DP[x + 1][y + 1];
         return DP[x][y];
      }
      DP[x][y] += func(x, y + 1, last) + DP[x + 1][y + 1];
   }
   else {
      if (y == last) {
         DP[x][y] = 1;
         return DP[x][y];
      }
      DP[x][y] += func(x, y + 1, last) + 1;
   }
   return DP[x][y];
}

int main(int argc, char *argv[])
{
   int cycle;
   cin >> cycle;

   while (cycle != 0) {
      init();
      cin >> west >> east;
      int last = east;
      int start = west;

      for (int i = west; i > 0; --i) {
         DP[i][i] = func(start, start, last);
         last--;
         start--;
      }

      cout << DP[1][1] << endl;
      --cycle;
   }

   return 0;
}