<백준 알고리즘> 20152번: Game Addiction

문제

강산이는 심각한 게임 중독자이기 때문에 날씨에 상관없이 매일 PC방을 간다.

최근에 폭우로 인해 일부 지역이 침수되어 침수된 지역으로는 이동할 수 없게 되었다. 하지만 강산이는 출석 이벤트를 위해 하루도 빠짐없이 PC방을 가야 한다.

강산이는 PC방까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동할 때의 거리는 1이다. 또한, 강산이는 게임을 빨리하러 가야 하기 때문에 집에서 PC방까지 최단경로로 움직인다.

강산이의 집의 좌표 (H, H)와 PC방의 좌표 (N, N)이 주어지고 좌표평면 위 (x, y)에서 y > x인 곳은 침수되었다고 할 때, 강산이가 침수된 지역을 피해서 PC방까지 갈 수 있는 경로의 개수를 구하라.

단, PC방의 좌표가 집의 좌표 같은 경우 경로는 1가지라고 한다.

입력

첫째 줄에 집과 PC방의 좌표 (H, H), (N, N) 을 나타내는 두 정수 H, N (0 ≤ H, N ≤ 30) 이 차례로 주어진다.

출력

집에서 PC방까지 갈 수 있는 경로의 개수를 출력한다.

예제 입력 1

8 4

예제 출력 1

14

예제 입력 2

0 3

예제 출력 2

5

---

Solution

#include<stdio.h>
#include<stdlib.h>

int main(void)
{
	int H, N;
	long **board=NULL;

	scanf("%d%d", &H, &N);

	if(H==N)
	{
		printf("1\n");
		return 0;
	}
	if(H>N)
	{
		H+=N;
		N=H-N;
		H-=N;
	}
	N-=H;
	H=0;

	board=(long **)malloc((N+2)*sizeof(long *));
	for(int n=0;n<N+2;n++)
		board[n]=(long *)calloc(N+2,sizeof(long));

	for(int i=1;i<N+2;i++)
	{
		board[0][i]=1;
		for(int j=1;j<=i;j++)
			board[i][j]=board[i-1][j]+board[i][j-1];
	}

	printf("%ld\n", board[N+1][N+1]);
	for(int n=0;n<N+2;n++)
		free(board[n]);
	free(board);
	return 0;
}