[알고리즘][Python] 백준(BOJ) 10164 격자상의 경로_파이썬

 

DP

10164 격자상의 경로    www.acmicpc.net/problem/10164

10164번: 격자상의 경로

 

 

문제 풀기 전 공부할 것 : 수학, 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• 구체적인 단계 풀이가 필요하신 분이 계시다면 댓글 부탁드립니다.

 

<코드>

n, m, o = map(int, input().split())
dp = [[0 for _ in range(m)] for _ in range(n)]
if o == 0:
    for i in range(n):
        for j in range(m):
            if i == 0:
                dp[i][j] = 1
            elif j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                
    print(dp[n-1][m-1])
else: 
    x, y = (o-1)//m, (o-1)%m
    for i in range(x+1):
        for j in range(y+1):
            if i == 0:
                dp[i][j] = 1
            elif j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                
    for i in range(x, n):
        for j in range(y, m):
            if i == x and j == y:
                continue
            elif i == x:
                dp[i][j] = 1
            elif j == y:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                
    print(dp[x][y] * dp[n-1][m-1])