백준 1890 점프

유형 : dp

 

 처음에는 dfs를 이용하여 모든 경로를 탐색했으나 당연히 시간초과가 나왔다.

문제풀이

1. dp를 활용해야 하는데, dp[r][c]는 (r,c)에 올 수 있는 경우의 수이다. (r,c)에서 갈 수 있는 길이가 a라 하면, (r+a,c), (r,c+a) 두 가지 경우가 가능하다. 두 경우 가능한 경우의 dp 값에 dp[r][c]를 더해주면 된다.

2. 1의 과정을 (0,0)부터 (n-1,n-1)까지 반복한다.

 

요약

 모든 경로를 다 고려할 필요 없이, dp를 이용하여 (r,c)에서 (r',c')으로 이동한다고 하면, dp[r'][c'] += dp[r][c]를 해주면 중복되는 경로들을 다시 탐색하지 않아도 된다.

 

Python Code

import sys
def solution():
    dp[0][0] = 1
    for r in range(n):
        for c in range(n):
            l = maps[r][c]
            if l == 0 or dp[r][c] == 0 :
                continue
            new_r = r+l
            new_c = c+l
            if new_r < n:
                dp[new_r][c] += dp[r][c]
            if new_c < n:
                dp[r][new_c] += dp[r][c]
    print(dp[n-1][n-1])
if __name__=="__main__":
    n = int(sys.stdin.readline())
    maps = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    dp=[[0 for i in range(n)] for j in range(n)]
    solution()

line 3 : 0,0에서 시작할 것이니, dp[0][0]은 0이 아닌 1로 해주어야한다.

line 7 : (r,c)에서 갈 수 있는 경우가 0이거나 (r,c)에 도착 할 수 있는 경우의 수가 0이라면 고려할 필요가 없다.

line 12, 14 : 위에서 언급한 dp[r'][c'] += dp[r][c] 과정.

 

 길이가 N인 정사각형에 대하여 이중 포문을 도므로 시간복잡도는 O(N^2)이 된다.

문제 링크

1890번: 점프