[백준] 10164번 격자상의 경로

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

• count는 k를 찾기 위해 설정

• k가 0이 아니면 k까지 가는 경우의 수와 k부터 끝점까지 가는 경우의 수를 곱해주면 된다.

# 10164 : 격자상의 경로

import sys
input = sys.stdin.readline

n, m, k = map(int, input().rstrip().split())

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][1], count = 1, 1

for i in range(1, n + 1):
    for j in range(1, m + 1):
        # k일 시 현재 위치 저장
        if count == k:
            sx = i
            sy = j
        # k 찾기 위해 1씩 증가
        count += 1
        # 아래로 가는 경우와 오른쪽으로 가는 경우 더하기
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

if k == 0:
    print(dp[n][m])
# k가 0이 아니면
# k위치까지 가는 경우의 수와 k부터 끝점까지 가는 경우의 수 곱하기
else:
    print(dp[sx][sy] * dp[n - sx + 1][m - sy + 1])

어려워서 다른사람들의 풀이를 보며 참고했습니다..

Uploaded by Notion2Tistory v1.1.0