python 백준 10164 격자상의 경로

• https://www.acmicpc.net/problem/10164

로직

- arr 구조

[1,1,1,1]
[1,2,3,4]
[1,3,6,10]
[1,4,10,20]

(0,0) 지점에서 (1,1)지점을 가는 경우의 수:

• (0,0) => (1,0) 1가지
• (0,0) => (0,1) 1가지
• (1,1)지점 가는 방법 = (1,0)에서 이동 + (0,1)에서 이동
• 각각의 한 칸 전 지점에 도달하는 방법의 수를 합하면 구할수 있다

특점 지점에 들리는 경우 계산

• (0,0) 에서 (r,c)지점에 들려야 하는 경우의 수 계산
• (r,c)에서 종점(N,M)에 들려야 하는 경우의 수 계산 = (0,0)에서 (N-r-1,M-c-1)도달 하는 경우의 수
• 두 경우의 수의 곱

N,M,K = map(int,input().split())
arr = [[0]*M for _ in range(N)]
for r in range(N):
    arr[r][0] = 1
for c in range(M):
    arr[0][c] = 1

def solution(r,c):
    if arr[r][c]:
        return arr[r][c]
    arr[r][c] = solution(r-1,c) + solution(r,c-1)
    return arr[r][c]

if K:
    r,c = (K-1)//M,(K-1)%M
    ans = solution(r,c) * solution(N-r-1,M-c-1)
else:
    ans = solution(r,c)
print(ans)