백준[ 1890 | Python ] 점프

문제

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

시도

시도는 DFS가 되었다.
그 이유는 이중 for문을 돌렸을 때 어차피 시작점은 0,0 이기 때문에,
의미 없는 값들이 탐색될 것이라고 판단했고 아직은 1차원적으로 생각하는데에 익숙해서 였다.
혹시했지만 역시 시간초과.

import sys
input = sys.stdin.readline
n = int(input().rstrip())
board = [list(map(int,input().split())) for _ in range(n)]
cnt = 0
def tracing(x,y):
    global cnt
    if x >= n or y >= n:
        return
    if board[x][y] == 0:
        cnt += 1
        return 
    tracing(board[x][y]+x, y)
    tracing(x, y+board[x][y])
tracing(0, 0)
print(cnt)

풀이

게임판[x][y]로 갈 수 있는 경우의 수를 갱신해가는 방법이다.
게임판의 각 칸들로 갈 수 있는 경우의 수를 2중 for 문으로 탐색한다.
그 과정에서 이동하려는 칸의 수가 n을 벗어나면 안되기 때문에 조건에 충족하는 수 일 경우에만
경우의 수를 갱신해준다.
마지막 칸에 도달한다면 마지막 칸에 갈 수 있는 경우의 수를 출력하고 종료한다.

import sys
input = sys.stdin.readline
n = int(input().rstrip())
board = [list(map(int,input().split())) for _ in range(n)]
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[i][j])
            break
        if i + board[i][j] < n:
            dp[i+board[i][j]][j] += dp[i][j]
        if j + board[i][j] < n:
            dp[i][j+board[i][j]] += dp[i][j]
print(dp)

생각 & 정리

DP테이블에는 원하는 결과값만이 올라가야 한다고 예전 메모에 기록해 두었는데,
생각보다 그 실천이 어렵다. 경우의 수를 어떻게 셀 수 있을지 고민을 많이 했던 문제였다.