[BOJ] 백준 1890. 점프

🥈점프

💡 아이디어

예제1을 따라 시뮬레이션을 해보자.

1. 0,0 값인 2가 3(4-1)보다 작다면, 2,0 과 0,2로 이동가능하다
2. 2,0(1)과 0,2(3)를 각각 시작값으로 두자
3. 2,0(1) 을 고려해보자. 각각의 x,y가 현재위치 + 좌표값 ≤ 3(4-1) 일 경우만 이동이 가능하다. 이때 3,0 과 2,1이 나온다.
4. 3,0(3) 을 고려해보자. 6,0 3,3 중에서 6은 불가하므로 3,3이 가능하고, 이는 곧 좌표의 맨 아래 끝값이 된다.

대충 정리해보면

1. x, y 각각의 좌표가 n-1이 될 경우 (끝 값에 도달할 경우) break 후 print
2. 좌표는 현재 좌표값을 기준으로 두가지 갈래로 구해나가고, 움직일 수 있는 길일 경우 전의 좌표를 바탕으로 dp값을 갱신해준다

🧑🏻‍💻 코드

# 백준 점프
n = int(input())

jump = []
for i in range(n):
    jump.append(list(map(int, input().split())))
    
dp = [[0] * n for i 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[i][j])
            break
        now = jump[i][j]
        
        if i + now < n:
            dp[i+now][j] += dp[i][j]
        
        if j + now < n:
            dp[i][j+now] += dp[i][j]

👍🏻 느낀점

찾은 규칙을 식으로 옮기는 과정을 많이 반복해야 할 것 같다.