[python] 백준 - 1890. 점프

🤔문제 해결

• S2 | DP

DFS로 해봤지만 역시나 시간초과!!

시간복잡도가 O(N^2) 인 DP로 풀어봤다.

 

dp에는 현재 위치까지 올 수 있는 경우의 수를 담아서 해결함.

 

 

💻소스 코드

N = int(input())
field = [list(map(int, input().split())) for _ in range(N)]
answer = 0

dp = [[0] * N for _ in range(N)]  # i,j까지 올 수 있는 경우의 수를 저장
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        if i == N - 1 and j == N - 1:  # 끝에 도달했을 때
            print(dp[i][j])
            break
        cur_cnt = field[i][j]
        # 오른쪽으로 가기
        if j + cur_cnt < N:
            dp[i][j + cur_cnt] += dp[i][j]
        # 아래로 가기
        if i + cur_cnt < N:
            dp[i + cur_cnt][j] += dp[i][j]

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

1890번: 점프