문제 내용만 보았을때는 시작점에서 갈수있는 위치를 저장하고 DFS/BFS 탐색으로 풀면 될것같다고 생각이 났다.
하지만 갈수 있는 위치를 저장하는 데이터의 개수가 너무 많아진다.
(0,0) 시작점을 제외하고 저장해야하는 데이터 개수는
2X2에서는 4개, 3X3에서는 12개, 4X4에서는 24개
...
100X100에서는 100x2^99
(약 2의 30승이 넘는다)
(게임판은 최소 4 X 4, 최대 100 X 100이다.)
제한시간은 1초이므로 이 아이디어는 n^2 시간복잡도를 가지는 알고리즘으로도 풀 수 없다.
위의 방식으로 저장하는 데이터가 점점 많아 지는 이유는 중복된 데이터가 n이 커질수록 더 많아지기 때문이다.
위에서 각 위치에서 갈 수 있는 위치를 저장하는 이유는 다음 반복에서 이전에 저장한 위치를 가지고 다음으로 이동할 위치를 저장하기 위해서였다.
➡️ 중복되는 데이터가 저장되고 이전에 저장한 값을 가지고 현재 저장할 값에 영향을 미치며 작은 부문제들이 큰 문제를 해결할 수 있으면 다이나믹 프로그래밍을 생각해 볼 수 있다.
다이나믹 프로그래밍 (DP)
import sys
input = sys.stdin.readline
n = int(input())
board = [list(map(int,input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1 # 초기화
for x in range(n):
for y in range(n):
now = board[x][y] # 현재 갈 수 있는 칸 개수
if x == y == n-1: # 마지막칸
print(dp[x][y])
break
down = x + now # 아래 이동
right = y + now # 오른쪽 이동
if down < n:
dp[down][y] += dp[x][y]
if right < n:
dp[x][right] += dp[x][y]코드 설명
dp : 이전 위치까지 도달되는 경로 수 + 현재 위치까지 도달되는 경로 수
반복문 : 시작점에서 갈 수 있는 모든 칸을 탐색
이중 반복 문으로 시간복잡도는 N^2 이며 실행 시간은 40ms가 나왔다.
