[알고리즘/동적 계획법] 1890번 : 점프 - python

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

1890번: 점프

 

---

• 문제
• 소요시간: 45분 10초

---

• 설계하기(접근방법) 

1. n과 리스트들을 입력받는다

2. 알고리즘 해석

이중배열을 통해서 문제를 해결해야 할 것이다

이동 방향은 오른쪽 혹은 아래로만 이동하므로

전체 이중배열을 순회하면서 

이동 가능한 좌표들에 한해서 이동 가능 경우의 수를 기록한다.

이와 같은 형태로 나타날 것이다

 

1) 현재 리스트의 위치 (graph[i][j])에서는 해당 값 만큼만 이동이 가능하다.

graph[0][0] = 2, 즉 오른쪽 혹은 아래로 2칸만큼 갈 수 있다

 

i) 칸을 이동했을 때 정사각형의 범위(n)을 넘어가는 경우는 이동 할 수 없다.

즉 이중배열의 x좌표가 n을 넘어가거나

y좌표가 n을 넘어가는 경우는

이동을 제한하는 조건을 if문으로 건다

-> ex) graph[2+3][0] 인 경우 기록 x

 

2) 리스트를 순회하며, 다음 칸으로 이동할 수 있는 경우에 현재 dp(이동가능한 경우의 수)를 다음 좌표에 더해서 이전한다.

ex)

2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 0 이 리스트가 있는 경우

 

dp는

0 0 1 0 1
0 0 0 0 0
1 0 2 0 3
0 0 0 0 0
1 0 3 0 6  이런 형태로 나타날 것이다

 

마지막 좌표인 dp[4][4]이 6이 된 이유는

dp[2][4] = 3에서 3이 더해졌고

dp[4][2] = 3에서 3이 더해져

총 6이 이전되었다.

 

3. dp[n-1][n-1] 끝지점의 좌표의 dp값을 출력한다

 

 

---

• 코드(출력)

n = int(input())
dp = [[0 for i in range(n)] for i in range(n)]
graph = []


for i in range(n):
    graph.append(list(map(int, input().split())))


dp[0][0] = 1

for i in range(n):
    for j in range(n):
        if i == n-1 and j == n-1:
            break
        m = graph[i][j]
        w = dp[i][j]
        if w > 0:
            if i + m < n:
                dp[i + m][j] += w
            if j + m < n:
                dp[i][j + m] += w

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

---

• 얻어갈 부분

1. 이중배열을 선언하여 문제를 푸는 실력이 예전보다 발전했다.

2. 문제가 복잡해보이는 경우, 처음부터 순회하면서 풀 수 있는지 먼저 체크해보자. 된다면 그 방법이 빅오를 만족하는지 계산해보고 시간초과에 해당하지 않는다면 밀고 나가자