백준 [1890]: 점프

📌 백준 [1890]: 점프

🔗 문제 링크

---

문제 설명 📄

N×N 크기의 게임판이 주어진다. 각 칸에는 해당 칸에서 이동할 수 있는 거리가 적혀 있다.
오른쪽 또는 아래쪽으로만 이동 가능하며, 도착점 (N-1, N-1)에 도달할 수 있는 경로의 개수를 구하시오.
시작점은 (0,0)이며, 도착점의 값은 항상 0이다.

---

문제 접근 방식 💡

• 재귀 + 메모이제이션을 사용하여 도착점까지의 경로 개수를 계산.
• dp[x][y]를 (x, y)에서 도착점까지 도달할 수 있는 경로의 수로 정의.
• 종료 조건:
  • (x, y)가 도착점이면 1 반환.
  • arr[x][y] == 0이면 이동 불가하므로 0 반환.
• 점화식:
  • 오른쪽과 아래쪽 이동을 고려해 dp[x][y] = count_paths(x + step, y) + count_paths(x, y + step)

---

Solution 💻

n = int(input())
arr = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[-1] * n for _ in range(n)]

def count_paths(x, y):
    if x == n - 1 and y == n - 1:
        return 1
    if arr[x][y] == 0:
        return 0

    if dp[x][y] != -1:
        return dp[x][y]

    paths = 0
    step = arr[x][y]

    if x + step < n:
        paths += count_paths(x + step, y)

    if y + step < n:
        paths += count_paths(x, y + step)

    dp[x][y] = paths
    return dp[x][y]

print(count_paths(0, 0))

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n^2)
  • 각 칸을 한 번만 방문하며 메모이제이션을 사용하여 중복 호출을 방지.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n^2)
  • DP 테이블과 재귀 호출 스택이 최대 n^2 크기로 사용됨.

---

리팩토링 🛠️

from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)

n = int(stdin.readline().strip())
arr = [list(map(int, stdin.readline().split())) for _ in range(n)]

dp = [[-1] * n for _ in range(n)]

def count_paths(x, y):
    if x == n - 1 and y == n - 1:
        return 1
    if arr[x][y] == 0:
        return 0

    if dp[x][y] != -1:
        return dp[x][y]

    step = arr[x][y]
    dp[x][y] = 0

    if x + step < n:
        dp[x][y] += count_paths(x + step, y)
    if y + step < n:
        dp[x][y] += count_paths(x, y + step)

    return dp[x][y]

print(count_paths(0, 0))

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n^2)
  • 중복 계산을 방지하여 최적화된 동적 계획법 사용.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n^2)
  • DP 테이블과 재귀 호출 스택이 최대 n^2 크기로 사용됨.