[백준1890] / 점프 - DP

 

백준1890

 

 

푼 날짜 : 2024.10.25

푼 문제 : [1890] / 점프

사용한 언어 : python

알고리즘 : DP

 

 

점화식 :

dp[i+num][j] += dp[i][j] (if i + num < N)
dp[i][j+num] += dp[i][j] (if j + num < N)

 

현재 위치에서 이동 가능 숫자(num)만큼 뛰었을 때 범위를 벗어나지 않는 경우 현재 값을 더해준다.

 

 

 

코드 :

N = int(input())

graph_ = []
for _ in range(N):
    row = list(map(int, input().split()))
    graph_.append(row)

dp = [[0 for _ in range(N)] for _ in range(N)]
dp[0][0]=1 # 가장 왼쪽 위 칸에서 출발하므로 시작 1로 초기화

for i in range(N):
    for j in range(N):
        if i == j == N-1: break # 도착 지점은 종료
        num = graph_[i][j] # 이동 거리를 계산하기 위함
        if num == 0: continue # 이동 가능 거리가 0 이면 패스
        if i + num < N: dp[i+num][j] += dp[i][j] # 아래로 가는 경우
        if j + num < N: dp[i][j+num] += dp[i][j] # 오른쪽으로 가는 경우

print(dp[-1][-1]) # 가장 오른쪽 아래 값 출력 (도착 지점)

 

 

사실 이런 2차원 배열을 만나게 되면 제일 먼저 떠오르는 것이 그래프이다.

하지만 단정 지어서는 안된다.

 

범위와 시간복잡도를 고려해서 적절한 알고리즘을 선택해야 한다.

아직은 그런 부분에서 부족하다고 느낀다. 

(처음에 BFS/DFS로 풀어야지! 라고 생각했다가 알고리즘 분류가 DP임을 확인하고 DP로 시작했다..)

 

시간 복잡도 관련해서도 공부를 다시 해야겠다고 느꼈다.