글 읽기 - 보드점프 질문드립니다.

kjho1037 6년 전 0

안녕하세요.

3372번 보드점프문제입니다.

1520 내리막길 문제랑 비슷한 것 같아 내리막 길에서 문자열로 처리해서 큰 수 A+B해답이랑

짬뽕시켯는데....14%에서 계속 틀리네요ㅜ,ㅠ

답변주시면 감사하겠습니다!!

#include <stdio.h>
#include <string.h>
#define StoD(X) (X==0?0:X-'0')

void reverse(char *, int );
char * add(char *,char *);

int N, map[101][101];
char DP[101][101][101] = {0};//y,x,문자열
char S[101] = { 0 };//덧셈을 위한 배열
char xx[3] = {NULL};
char yy[3] = {'1',};

char * D(int y, int x)
{
	//memset(aa, -1, sizeof(aa));	memset(bb, 0, sizeof(bb));
	
    if (DP[y][x][0] != NULL)//배열에 저장된 값이 있으면 return DP[y][x]
		return DP[y][x];

	if (y==N && x==N)//목적지에 도착하면 return 1
		return yy;

	if (map[y][x] == -1|| map[y][x] == 0)//입력된 범위를 벗어나거나 0인 지점에서는 return 0
		return xx;

	strcpy(DP[y][x], add(D(y, x + map[y][x]),D(y + map[y][x], x)));
	
	return DP[y][x];
}

int main()
{
	memset(map,-1,sizeof(map));
	scanf("%d",&N);
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			scanf("%d", &map[i][j]);

	printf("%s",D(1,1));

	return 0;
}

char * add(char * A, char * B)//문자열 더하기
{
	int len = 0, up = 0;
	memset(S,0,sizeof(S));
	if (strlen(A) > strlen(B))
		len = strlen(A);
	else
		len = strlen(B);

	reverse(A,strlen(A));
	reverse(B,strlen(B));

	for (int i = 0; i <= len; i++)
	{
		S[i] = (StoD(A[i]) + StoD(B[i]) + up) % 10 + '0';
		if ((StoD(A[i]) + StoD(B[i]) + up) > 9)up = 1;
		else up = 0;
	}
	if (S[len] == '0') S[len] = 0;

	reverse(S, strlen(S));

	return S;
}

void reverse(char * arr, int len)//문자열 뒤집기
{
	char temp;

	for (int i = 0; i < len / 2; i++)
	{
		temp = arr[i];
		arr[i] = arr[len-1-i];
		arr[len - 1 - i] = temp;
	}
	return;
}