글 읽기 - 1890번 점프 질문합니다.

waylight3 8년 전 0

DP로 풀었는데, (0, 0)에서 (mapSize-1, mapSize-1)까지 오른쪽 또는 아래쪽으로 이동하는 것을 재귀적으로 짰습니다.

그런데 이 코드를 제출했더니 런타임 에러가 뜨더라구요...

혹시나 해서 12번째 줄의 if문 조건을 map[y][x] == 0 으로 바꾸었더니 이번엔 틀렸습니다라고...

도중에 0이 나타날 수 있으니 당연히 정답일리는 없겠지만, 일단 런타임 에러가 안떴다는걸 알 수 있었습니다.

근데 어차피 맨 오른쪽 아래가 출구이고 0이 적혀있을 거라면 제가 처음에 제출한 코드에 어떤 문제가 있는지 모르겠습니다 ㅠㅠ

#include <iostream>
#include <algorithm>
using namespace std;

long long map[101][101];
long long ans[101][101];
long long mapSize;

long long jump(long long x, long long y)
{
	if (x < 0 || x > mapSize - 1 || y < 0 || y > mapSize - 1) { return 0; }
	if (x == mapSize - 1 && y == mapSize - 1) { return 1; }
	if (ans[y][x] != -1) { return ans[y][x]; }
	return ans[y][x] = jump(x + map[y][x], y) + jump(x, y + map[y][x]);
}

int main() {
	cin >> mapSize;

	for (int i = 0; i < 101; i++)
	{
		for (int j = 0; j < 101; j++)
		{
			ans[i][j] = -1;
		}
	}

	for (int i = 0; i < mapSize; i++)
	{
		for (int j = 0; j < mapSize; j++)
		{
			cin >> map[i][j];
		}
	}

	cout << jump(0, 0);

	return 0;
}

yukariko 8년 전 0

중간에 0이 존재하면 0칸 점프해야 하는데, 그 과정으로 인해서 계속 같은 좌표를 반복하게 되어

stack overflow가 발생하는것 같습니다.

0일때의 특별한 처리가 필요해 보이네요.

waylight3 8년 전 0

0이 있으면 거기에서 계속 멈춰있던 거였군요!

그런데 map[y][x]가 0이면 재귀호출 하는 걸 막고자 0을 리턴하도록 수정해도 여전히 런타임 에러가 뜨네요 ㅠㅠ

#include <iostream>
#include <algorithm>
using namespace std;

long long map[101][101];
long long ans[101][101];
long long mapSize;

long long jump(long long x, long long y)
{
	if (x < 0 || x > mapSize - 1 || y < 0 || y > mapSize - 1) { return 0; }
	if (x == mapSize - 1 && y == mapSize - 1) { return 1; }
	if (ans[y][x] != -1) { return ans[y][x]; }
	if (ans[y][x] == 0) { return ans[y][x] = 0; }
	return ans[y][x] = jump(x + map[y][x], y) + jump(x, y + map[y][x]);
}

int main() {
	cin >> mapSize;

	for (int i = 0; i < 101; i++)
	{
		for (int j = 0; j < 101; j++)
		{
			ans[i][j] = -1;
		}
	}

	for (int i = 0; i < mapSize; i++)
	{
		for (int j = 0; j < mapSize; j++)
		{
			cin >> map[i][j];
		}
	}

	cout << jump(0, 0);

	return 0;
}

yukariko 8년 전 0

ans[y][x]가 아니라 map[y][x]가 0이 되어야 할겁니다

waylight3 8년 전 0

아 제가 쓰고도 오타난 줄 몰랐네요 ㅎㅎ

감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1890번 점프 질문합니다.

waylight3 8년 전 0

yukariko 8년 전 0

waylight3 8년 전 0

yukariko 8년 전 0

waylight3 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말