[백준 1010번] 다리 놓기

---

BOJ 1010번 다리놓기 

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

백준 1010번 C++ 소스

DP배열을  0으로 초기화할때 memset(DP, 0, sizeof(DP)); 으로 제출했더니 컴파일 에러가나서

int DP[33][33] = { 0 }; 이렇게 초기화 했다.

i는 N을 컨트롤하는 변수이며, j는 M을 컨트롤 하는 변수이다.

코드 18번째 줄에서 DP[1][i] 를 모두 오른쪽 다리의 개수로 대입한다.

i가 1이면 j값에 따라서 경우의 수 값이 결정되기 때문이다. 

코드 25번째 줄에서 i가 최소 2부터 시작하므로 j도 최소 2부터 시작한다.

입력범위 N, M (0 < N ≤ M < 30)를 참고했을 때  i=2, j=1 이렇게는 시작할 수 없기 때문이다.

  j가 i보다 항상 같거나 크다고 해서 코드 25번째 라인 for부분을  j=i로 시작하면 안된다.

 예를들어 DP[4][3]을 구할 때 점화식 특성상 DP[3][2]가 필요하게 되는데, 

이 부분은 맨 밑 예시설명에 DP[3][4] 루프순서를 보게되면 왜 안되는지 알 수 있을 것이다.  

   ( j=i로 해버리면 DP[3][2]를 안구하고 skip해버림 )

이 문제는 아래 2가지경우 처럼 다리 놓는것은 허용되지 않는다.

---

---

허용되지 않는 경우의 수를 알았으니 이제 DP[2][2]부터 구해보자. 

DP[2][2] = DP[1][1] 이다.

맨 위를 서로 연결하고, 나머지 경우의 수를 따져보면 1, 1밖에 남지 않기 떄문에 

DP[2][2] = DP[1][1]가 된다. 

---

DP[2][3] 구해보자. 

DP[2][3]은 아래 그림과 같이 

먼저 맨 위를 하나 먼저 긋고 1, 2인 경우의 수를 구한다.

그 다음 서쪽 i에 해당하는 부분 맨 위쪽과  동쪽 j에서 맨 위에서 두번째 부분을 연결한다. 

그럼 1, 1인 경우의 수만 남을 것이다. 

따라서 DP[2][3] = DP[1][2] + DP[1][1]가 된다.

---

DP[2][4] 구해보자. 

DP[2][4]은 아래 그림과 같이 

맨 위를 하나 먼저 긋고 1, 3인 경우의 수를 먼저 구한다.

그 다음 서쪽 i에 해당하는 부분 맨 위쪽과  동쪽 j에서 맨 위에서 두번째 부분을 연결한다. 

그럼 1, 2인 경우의 수를 구하면 될 것이다.

마지막으로 그 다음과정을 거치면 아래 그림 맨 오른쪽과 같이  1, 1인 경우의 수만 남을 것이다.

여기서 점화식을 세울 수 있다.  바로 전 단계에서 구한  DP[2][3] = DP[1][2] + DP[1][1]  이 부분이다. 

DP[1][1] + DP [1][2]를 DP[2][3]으로 치환하고 나머지 부분 DP[1][3]만 더해주면 DP[2][4]가 완성된다.

따라서 DP[2][4] = DP[2][3] + DP[1][3]가 되고, 

점화식은 DP[i][j] = DP[i][j-1] + DP[i-1][j-1]으로 세울 수 있다.

---

DP[3][4]를 구한다고 해보자. 

그럼 반복문은 2,2 --> 2,3 --> 3,2 --> 3,3 --> 3,4 이 순서로 루프를 돌게 되는데,

DP[3][4] = DP[2][3] + DP[3][3] 인데,  DP[2][3]은 위 예시과정에서 구했고 DP[3][3]은 바로 전 단계 루프이므로 

누락되는 값 없이  정상적으로 답을 구할 수 있게 된다.

---

---

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
	int N, M, i, j, T;
	int DP[33][33] = { 0 };

	cin >> T;
	while (T--)
	{
		cin >> N >> M;

		for (i = 1; i <= M; i++)
		{
			DP[1][i] = i;
		}

		for (i = 2; i <= N; i++)
		{
			for (j = 2; j <= M; j++)
			{
				DP[i][j] = DP[i - 1][j - 1] + DP[i][j - 1];
			}
		}
		cout << DP[N][M] << endl;
	}
}