[백준 10164] 격자상의 경로

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

10164번: 격자상의 경로

---

접근

만약 O 표시가 없을 때는 특정 위치 (i, j) 까지 이동할 수 있는 경우의 수를 구하기 위해서는 해당 위치의 위쪽과 왼쪽의 경우의 수를 더하면 된다. 왜냐하면 오른쪽과 아래로만 이동할 수 있고 두 방향의 경우의 수를 더하면 해당 위치까지 이동할 수 있는 경우의 수가 나온다.

 

이때 O표시가 있을 때는 (1, 1)위치부터 O 표시가 있는 위치까지의 경우의 수 X O 표시가 있는 위치부터 (N, M)까지의 경우의 수가 된다. 

 

구현

• 해당 위치의 경우의 수를 저장할 수 있는 2차원 리스트인 dp를 0으로 초기화하여 생성한다.
• (1, 1)부터 탐색을 진행하기 때문에 (1, 0) 또는 (0, 1)을 1로 초기화해준다.
• step은 K를 찾기위함이다.
• (1, 1)부터 탐색을 진행하고 왼쪽과 위쪽의 경우의 수를 더하여 현재 위치에 저장한다.
• 그리고 step을 증가시켜서 K를 찾고 K일 때는 해당 위치를 저장한다.
• 이제 K가 0이 아닐 때는 (1, 1)부터 (sy, sx)까지의 경우의 수인 dp[sy][sx]와 (sy, sx)부터 (N, M)까지의 경우의 수인 dp[N-sy+1][M-sx+1]을 곱한다.
• K가 0일 때는 DP[N][M]을 출력하면된다.

N, M, K = map(int, input().split())

dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
dp[0][1], step = 1, 1
sy, sx = 0, 0

for i in range(1, N + 1):
    for j in range(1, M + 1):
        if step == K:
            sy, sx = i, j
        step += 1
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

answer = dp[sy][sx] * dp[N - sy + 1][M - sx + 1] if K else dp[N][M]

print(answer)