[백준 1890번] 점프 - Python

문제

1890번: 점프

 

 

---

풀이

import sys
input = sys.stdin.readline

n = int(input())

game_map = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * n for _ in range(n)]

dp[0][0] = 1

def move():
    for i in range(n):
        for j in range(n):
            k = game_map[i][j]

            if k == 0:
                continue

            # 아래로 이동
            if i+k < n:
                dp[i+k][j] += dp[i][j]

            # 오른쪽으로 이동
            if j+k < n:
                dp[i][j+k] += dp[i][j]
    return dp[-1][-1]
print(move())

 

bfs로 처음에 접근했다가 안풀려서 고민하다 풀이를 보았다.

dp로 풀면 생각보다 간단하다.

 

아이디어

• dp를 주어진 n * n만큼 0으로 초기화하고 dp[0][0] = 1(출발지)로 설정해준다.
• 해당 칸에서 아래(i+k) 혹은 오른쪽(j+k)으로 이동시 게임판 범위 안에 들어간다면 해당 위치 dp에 현재 위치 dp 값을 더해준다. (dp[i+k][j] += dp[i][j], 즉 + 1)
• 게임판의 0에 도달하면 이동을 멈춘다.
• dp의 마지막 칸에 도달할 수 있는 경로의 수가 +1씩 되어서 자동으로 담긴다.
• 가장 오른쪽 아래 칸 (n-1, n-1)을 출력한다.

---

 

참고

https://code-angie.tistory.com/12