https://www.acmicpc.net/problem/10164
코드
n, m, k = map(int, input().split())
def find_path(r, c): # 세로 길이가 r, 가로 길이가 c인 격자에서 경로의 개수 구하기
dp = [[0]*(c) for _ in range(r)]
dp[0][0] = 1
for i in range(r):
for j in range(c):
if i+1 < r:
dp[i+1][j] += dp[i][j]
if j+1 < c:
dp[i][j+1] += dp[i][j]
return dp[r-1][c-1]
if k == 0:
print(find_path(n, m))
else:
r = (k-1)//m
c = (k-1) % m
# k에 도달할 때까지의 경우의 수
prev = find_path(r+1, c+1)
# k부터 N X M까지의 경우의 수
next = find_path(n-r, m-c)
print(prev*next)
풀이
목적지까지 경로의 개수 구하는데 중간에 꼭 경유해야 하는 곳이 있다면 다음과 같이 출발지-경유지까지 가는 길과 경유지-목적지까지 가는 길의 경로의 수를 각각 구해서 곱하면 된다.
1번이 출발지, 15번이 목적지, 8번이 경유지라면 (1번에서 8번까지 가는 경우의 수) × (8번에서 15번까지 가는 경우의 수)를 구하면 문제에서 요구하는 답을 구할 수 있다.
그렇기 때문에 직사각형이 있을 때 왼쪽 위에서 오른쪽 아래까지 가는 경우의 수를 리턴하는 함수 `find_path()`를 구현했다. find_path()는 각 칸까지 가는 경로의 수를 저장하는 dp 배열을 이용하여 오른쪽 아래까지의 경로를 구한다.
이제 주어진 N×M 사각형에서 경유지를 가장 오른쪽 아래 칸으로 포함하는 직사각형과 경유지가 가장 왼쪽 위에 오는 직사각형 하나로 나누어서 find_path() 함수를 적용하면 문제를 해결할 수 있다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 17212번 달나라 토끼를 위한 구매대금 지불 도우미 (0) | 2024.06.22 |
---|---|
[Python/파이썬] 백준 20364번 부동산 다툼 (0) | 2024.06.21 |
[Python/파이썬] 백준 5569번 출근 경로 (0) | 2024.05.26 |
[Python/파이썬] 백준 15990번 1, 2, 3 더하기 5 (0) | 2024.05.23 |
[Python/파이썬] 백준 4097번 수익 (1) | 2024.05.15 |