백준 9251 점프 문제풀이

문제 

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

1890번: 점프

 

 

 

문제 접근 방식

예전 수학 문제에서  아래와 같은 문제가 있었는데 이 문제와 유사하다. 

게임 판과 똑같은 크기의 메모이제이션 배열 d를 만들고 d를 아래와 같이 정의한다

d[ i ][ j ] = i, j 로 갈 수 있는 모든 경우의 수

 

이렇게 d를 정의할 경우 아래와 같은 점화식을 얻을 수 있다.

현재위치에서 뛸 수 있는 모든 경우의 수를 다음 위치의 경우에 수에 더해주는 방식으로 진행된다.

 

d[i+n][ j ] += d[ i ][ j ] ( i+n 이 보드내에 존재할 때)

d[ i ][ j +n ] += d[ i ][ j ] ( j+n 이 보드내에 존재할 때)

 

시간 복잡도

게임판의 행, 열을 모두 순회해야하기 때문에 O(n^2) 이 걸리며, n의 최댓값이 100이므로 시간 내에 동작함을 알 수 있다.

 

 

코드

if __name__=='__main__':
    n=int(input())
    board=[list(map(int,input().split())) for _ in range(n)]

    # d[i][j] = i,j 번째로 올 수 있는 모든 경우의 수
    d=[[0 for _ in range(n)] for _ in range(n)]
    d[0][0]=1
    for i in range(n):
        for j in range(n):
            if board[i][j]==0:
                continue

            ny=i+board[i][j]
            nx=j+board[i][j]
            if ny<n:
                d[ny][j]+=d[i][j]
            if nx<n:
                d[i][nx]+=d[i][j]
    print(d[n-1][n-1])