CEO

문제 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 문제 풀이 N X N 게임판이 주어질 때, 현재 경로에서 (0, 1), (1, 0)으로만 이동할 수 있다. 게임판에 주어진 숫자만큼 점프하여 이동하는 규칙이 적용될 때, (N, N)에 도달할 수 있는 경우의 수를 반환하는 문제이다. 이 문제는 단순히 보면 DFS나, BFS로 풀면 되겠지라고 생각되지만 N이 최대 100까지 커지므로 시간 초과가 발생하게 된다. 따라서 문제 분류와 같이 DP로 풀어야 한다. 현재 위치의 점프할 수 있는 거리를 x, y축에 각각..