[python]1890번 점프

이 문제는 점화식 보다는 직접 구현을 통해 경우의 수를 구했다.

칸에 있는 숫자를 x,y좌표에 더해서, 그 좌표가 게임판 안에 있다면 경우의 수를 누적해주면서 

모든 칸들을 탐색하였다.

그러면 마지막 칸의 누적된 경우의 수를 출력하면 왼쪽 위 부터 오른쪽 아래로 가는 모든 경우의 수가 출력된다.

 

size = int(input())
stg = [] #게임판 값들 저장
rst = [[0 for i in range(size)]for j in range(size)] #게임판 이동 경우의 수 저장하는 곳
rst[0][0] = 1 #맨처음 칸은 시작칸이기에 경우의 수 1가지
for i in range(size):
    stg.append(list(map(int,input().split())))
for i in range(size):
    for j in range(size):
        if not stg[i][j]:  #마지막 칸에 도달했을 시
            continue
        elif rst[i][j]:
            x = j+stg[i][j]  #오른쪽
            y = i+stg[i][j]  #아래
            if 0<=x<size: # 게임 판 안에 있을 시
                rst[i][x]+=rst[i][j] #경우의 수 누적
            if 0<=y<size: # 게임 판 안에 있을 시
                rst[y][j]+=rst[i][j]  #경우의 수 누적
print(rst[size-1][size-1]) #마지막 칸으로 도달하는 경우의 수 출력