[Python] 백준 #1890- 점프

문제

---

1890번: 점프

코드

---

My answer(시간초과)-재귀

def find_route(x,y,tmp,lim,cnt):
    if(x>=lim or y>=lim or tmp[x][y]==0):
        if(x==lim-1 and y==lim-1):
            return 1
        return 0
    elif(x==lim-1 and y==lim-1):
        return 1
    else:
        if(x+tmp[x][y]<=lim-1):
            cnt+=find_route(x+tmp[x][y],y,tmp,lim,0)
        if(y+tmp[x][y]<=lim-1):
            cnt+=find_route(x,y+tmp[x][y],tmp,lim,0)
        return cnt
    
import sys
input=sys.stdin.readline

n=int(input())
tmp=[]

for i in range(n):
    tmp.append(list(map(int,input().split())))
x,y,val=0,0,0
print(find_route(0,0,tmp,n,0))

My answer-dp

import sys
input=sys.stdin.readline

n=int(input())
tmp,dp=[],[]
for i in range(n):
    tmp.append(list(map(int,input().split())))
    dp.append([0]*n)
dp[0][0]=1

if(tmp[0][0]==0):
    print(0)
else:
    for i in range(n):
        for j in range(n):
            if(i==n-1 and j==n-1):
                break
            if(dp[i][j]==0):
                continue
            val=tmp[i][j]
            if(i+val<n):
                if(dp[i][j]!=0):
                    dp[i+val][j]+=dp[i][j]
                else:
                    dp[i+val][j]+=1
            if(j+val<n):
                if(dp[i][j]!=0):
                    dp[i][j+val]+=dp[i][j]
                else:
                    dp[i][j+val]+=1
    
    print(dp[n-1][n-1])

Another answer

N=int(input());m,dp=[],[x[:] for x in [[0]*N]*N];dp[0][0]=1
for i in range(N):m+=[list(map(int,input().split()))]
for y in range(N):
 for x in range(N):
  if dp[y][x]:
    k=m[y][x]
    if k>0:
     if x+k<N:dp[y][x+k]+=dp[y][x]
     if y+k<N: dp[y+k][x]+=dp[y][x]
print(dp[-1][-1])

 

풀이

---

내 첫번째 코드는 시간초과다 풀이는 맞는 것 같은데 재귀로 풀어서 그런거같다. 질문글들을 보니 문제에서 범위를 정해준 문제는 대부분 그 값까지 가도록 테스트케이스를 만들어놓은거고 그 숫자까지 재귀로 간다고 예상해보면 시간초과가 날지 안날지 알 수 있다고 한다. 즉 이 문제는 2의 63승까지 테스트케이스가 제공되고 그 숫자까지 재귀로 하나하나 모두 해본다는 것은 불가능하므로 이 문제는 재귀가 아닌 다른 방법으로 문제를 풀어야 된다는 것이다. 두번째 코드는 dp로 정상적으로 풀었다. 메모제이션을 하면서 한번온 길은 다시 돌아가지 않는다. 아래코드와도 거의 동일한 것 같다.