Baekjoon1890-점프

백준 사이트 1890 - 점프 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
백준에서는 Sliver2 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 습관이 참 무섭습니다. MAP + 값저장 ? = BFS + DP다 라고 생각하면 푸는 순간 꼬입니다.
  • BFS로 풀기가 힘든게 중복 방문처리에 대한 처리를 고려해줘야합니다. 따라서 DFS로 푸는게 낫긴합니다.
• 생각해보니 이 문제의 좌표의 움직임은 for문을 2번 돌린다하면 지나왔던 점은 신경을 안쓴다 입니다.
  • 아래와 오른쪽으로만 이동하니 지나왔던 (위, 왼쪽) 은 건들일이 없다는 것입니다.
• 순차적으로 돌아도 시간초과가 뜨는 지는 모르나 굳이 그래줄 필요는 없기에 간단한 분기문을 통해 걸렀습니다.
• 그리고 조심해야할 것이 문제에 대놓고 2^63-1의 이하값이 결과로 주어진다 했기에 자료형을 잘 생각해야합니다.

---

5. code

#include<queue>
#include<iostream>

using namespace std;

const int MAX = 101;
int MAP[MAX][MAX] = { 0, };
long long DP[MAX][MAX] = { 0, };
int N;
void Input()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
			cin >> MAP[i][j];
	}
}

void Solve()
{
	DP[0][0] = 1;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (DP[i][j] == 0 || (i == N - 1 && j == N - 1))
				continue;
			else
			{
				int range = MAP[i][j];
				int newX = i + range;
				int newY = j + range;
				if (newX < N) DP[newX][j] += DP[i][j];
				if (newY < N) DP[i][newY] += DP[i][j];
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	Solve();
	cout << DP[N - 1][N - 1];

	return 0;
}

---

6. 후기

처음에 BFS + DP로 풀려고하니 계속 틀려서 삽질을 많이했습니다.