[백준] 격자상의 경로

출처:: www.acmicpc.net/problem/10164

분류:: dp

 

1. 문제 이해 및 해결과정

- k가 0이 아니라면, 빨간 네모의 경우와 파란네모의 경우를 찾아 각각 곱해주면 되는데 - 파란 네모의 경우는 번호(8)를 기준으로 다시 초기화되어서 dp배열을 만들게 되므로 곧 다시 빨간 네모dp테이블과 같다

 

2. 풀이방법

 1.dp

#격자상의 경로
#https://www.acmicpc.net/problem/10164
import sys
sys.stdin = open("input.txt","r")
n,m,k=map(int,input().split())
dp=[[0]*(m+1) for _ in range(n+1)]
dp[0][1]=1
cnt=1
for i in range(1,n+1):
    for j in range(1,m+1):
        if cnt==k:
            pos_h=i
            pos_w=j
        cnt+=1
        dp[i][j]=dp[i-1][j]+dp[i][j-1]
if k==0:
    print(dp[n][m])
else:
    print(dp[pos_h][pos_w]*dp[n-pos_h+1][m-pos_w+1])
for i in range(n+1):
    print(dp[i])

 

3. 오답원인

 

4. 알게된 점