[백준] 1890번:점프 (python 파이썬)

문제

www.acmicpc.net/problem/1890

1890번: 점프

 

풀이 및 소스코드

처음엔 bfs로 arr[n-1][n-1]까지 가는 경우의 수를 구해주려 했으나

메모리 초과가 떴다 ㅠㅠㅠ 코드는 아래와 같았다.

import sys
from collections import deque
input = sys.stdin.readline

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

que = deque()
que.append([0,0])
res = 0
while que:
    nowx, nowy  = que.popleft()
    if nowx==n-1 and nowy==n-1:
        res += 1
        continue
    if nowx+arr[nowy][nowx]<n:
        que.append([nowx+arr[nowy][nowx], nowy])
    if nowy+arr[nowy][nowx]<n:
        que.append([ nowx, nowy+arr[nowy][nowx]])

print(res)

 

 

그래서 dp로 풀어주기로 했다.

사실 dp 문제긴 하지만 dp로 풀기싫었는데... 풀 수 밖에 없었다.

dp 배열을 dp[0][0] 만 1로 나머지 다 0으로 초기화 시켜줬다.

그리고 x, y 가 n-1인 경우엔 dp[-1][-1]을 출력해줬고, 

시간을 조금이나마 단축하기 위해서 dp[y][x]가 1보다 큰 경우에만 돌려줬다.

import sys
from collections import deque
input = sys.stdin.readline

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

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

for y in range(n):
    for x in range(n):
        if y == n-1 and x == n-1:
            break
        if dp[y][x]>=1:
            dy = y+arr[y][x]
            dx = x+arr[y][x]
            if 0<=dy<n:
                dp[dy][x] += dp[y][x]
            if 0<=dx<n:
                dp[y][dx] += dp[y][x]

print(dp[-1][-1])