[백준 문제풀이] 얼렁뚱땅 1890 점프 풀이

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

1890번: 점프

 

# BFS : 시간초과

- 이 문제를 보고 어떻게 DP로 푸는 생각을 할까?

from collections import deque
n = int(input())

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

q = deque()
q.append([0,0])

visited = [[0]*n for _ in range(n)]
visited[0][0] = 1

dx = [0, 1]
dy = [1, 0]

while q :
    x, y = q.popleft()

    for i in range(2) :
        nx = x + arr[x][y]*dx[i]
        ny = y + arr[x][y]*dy[i]
        if 0<=nx<n and 0<=ny<n :
            if visited[nx][ny] == 0 :
                visited[nx][ny] = visited[x][y]
                if (nx != n-1) or (ny != n-1) :
                    q.append([nx,ny])
            else :
                visited[nx][ny] += visited[x][y]
                if (nx != n-1) or (ny != n-1) :
                    q.append([nx,ny])

print(visited[n-1][n-1])

 

# DP : 통과

- 근데, 아니 ㅡ3ㅡ .. .... ...

- 생각한 로직은 비슷한거 같은데 (더하는거) 이 문제를 보고 어떻게 dp라고 생각하는걸까?

- 그냥 틀려야 하는걸까? .....

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

visited = [[0]*n for _ in range(n)]
visited[0][0] = 1

for i in range(n) :
    for j in range(n) :
        if i == n-1 and j == n-1 :
            print(visited[i][j])
        if j + arr[i][j] < n :
            visited[i][j+arr[i][j]] += visited[i][j]
        if i + arr[i][j] < n :
            visited[i+arr[i][j]][j] += visited[i][j]