BOJ(점프)(1890)

작성일 | In

점프 1890

  • NxN 게임 판에 수가 적혀져 있음
  • 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것
  • 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미
  • 반드시 오른쪽이나 아래쪽으로만 이동
  • 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야함
  • 가장 왼쪽 위에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 문제

풀이과정

방법 1

  • D[i][j] = (i,j) 칸에 올 수 있는 경로의 개수
  • (i,j) 칸에 올 수 있는 칸을 찾아야 한다.
  • 그렇다면 (i,k)에서 (i,j)로 갔다면 (왼쪽에서 오른쪽으로 갔다고 한다면)
  • k의 범위는 1<=k<j가 되며
  • j-k == A[i][k]이다.
  • 위에서 아래로 갔다고 한다면(k,j) -> (i,j)로 갔다면
  • k의 범위는 1<=k<i
  • i-k == A[k][j]

방법 2

  • 첫 번째 방법은 중복된 검사를 너무 많이 한다.(O(n^3))

  • 두 개의 각각의 칸은 갈 수 있는게 2개니까. 이 정보를 이용해서 테이블을 채울 수 있다.

  • D[i][j] = (i,j) 칸에 올 수 있는 경로의 개수
  • (i,j)에서 갈 수 있는 칸을 찾아야 한다.
  • (i,j)에서 오른쪽으로 가는 경우 D[i][j+A[i][j]] += D[i][j]
  • (i,j)에서 왼쪽으로 가는 경우 D[i+A[i][j]] += D[i][j]
  • 이 방법은 O(n^2)
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
d = [[0]*n for _ in range(n)]
d[0][0] = 1
for i in range(n):
    for j in range(n):
        if a[i][j] == 0:
            continue
        if j + a[i][j] < n:
            d[i][j+a[i][j]] += d[i][j]
        if i + a[i][j] < n:
            d[i+a[i][j]][j] += d[i][j]
print(d[n-1][n-1])

참고자료 codeplus

0%