백준 10164 격자상의 경로

풀이 과정

• 행과 열에 맞게 1로 가득 찬 2차원 배열을 만든다.
• 꼭 지나야하는 값의 좌표를 구한다.
  • 열의 수로 나눈 값의 몫과 나머지가 y, x 좌표가 된다.
• 2차원 dp로 해당 위치까지 가능한 이동 경로 수를 더해나간다.
  • 위 칸의 값과 왼쪽 칸의 값을 합한 값이다.

반례

1 1 1

답: 1

5 5 20

답: 35

• 문제가 발생하는 이유는 꼭 가야하는 칸의 좌표를 구할 때, 그냥 나눈 몫과 나머지를 취했기 때문이다.
• 그림에서는 1부터 시작하지만 실제로는 0부터 시작하므로 -1을 한 다음 몫과 나머지를 구해야한다.

N, M, essen = map(int, input().split())
dp = [[1] * M for _ in range(N)]
if essen != 0:
    y, x = divmod(essen-1, M)
    # y = essen // M
    # x = essen % M
    # x -= 1
    for i in range(M):
        for j in range(N):
            if (i > x and j < y) or (i < x and j > y):
                dp[j][i] = 0
    print(x, y)
# 필수로 지나야하는 위치를 구하기

for i in range(N):
    for j in range(M):
        if dp[i][j] == 0:
            continue
        if i == 0 and j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = dp[i][j - 1]
        elif j == 0:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
print(dp[-1][-1])