[백준]1890 점프(Python)

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

1890번: 점프

 

문제 접근

 

game[0][0]에서 game[N-1][N-1]로 가야 한다. 

만약 game[i][j] = k 라면, k 만큼의 이동이 다음 i+k 인가 i+j 인가

처음 이 문제가 dp인지 몰랐다면 끝까지 몰랐을 것 같은..? 

그러면 dp 점화식을 어떻게 정의할 것인가...

 

그동안 풀어왔던 문제처럼 dp[i][j]는 (i,j) 위치에 도달하기 위한 경로의 수를 저장

 

	j=0	j=1	j=2	j=3
i=0	2	3	3	1
i=1	1	2	1	3
i=2	1	2	3	1
i=3	3	1	1	0

 

(i, j)에서 오른쪽으로 k만큼 이동할 수 있다면 dp[i][j+k] 

(i, j)에서 아래로 k만큼 이동할 수 있다면 dp[i+k][j]

 

코드

import sys
input = sys.stdin.readline

N = int(input())

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

# game[0][0]에서 game[2][2]로 가야함
# game[i][j] = k라면 k만큼의 이동이 다음번 i+k이냐 아니면 i+j이냐..
# 이게 왜 dp문제죠..?
# 몰라 우선 이차원 dp 테이블 만들어

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

for i in range(N):
    for j in range(N):
        if i == N-1 and j == N-1:
            print(dp[N-1][N-1])
            break

        k = game[i][j]

        if j + k < N:
            dp[i][j+k] += dp[i][j]

        if i + k < N:
            dp[i+k][j] += dp[i][j]

 

문제 회고

 

역시나 중요한 것은 (i, j)에 도달(포함) 하기 위한 방법의 수를 누적해서 더해 나가고 결국 마지막 격자에 해당하는 dp[N-1][N-1]의 값을 출력하면 결국 (i-1, j-1)에 도달하기 위한 모든 경우의 수이다. LCS 문제와 달리 이차원 DP 문제의 기본 같다는 생각이 들었다.