인프런 커뮤니티 질문&답변

안녕하세요. zzzzz님.

1. 첫 번째 행의 경우

• 시작점 (0,0)에서 첫 번째 행의 다른 칸 (0, j)으로 가려면 오른쪽으로만 이동할 수 있습니다.

• 오른쪽으로만 이동하는 경우, 선택의 여지가 없으므로 경로는 유일하게 1가지입니다.

• 따라서 dp[0][j] = 1 (모든 j)가 됩니다.

2. 첫 번째 열의 경우

• 마찬가지로, (0,0)에서 첫 번째 열의 다른 칸 (i, 0)으로 가려면 아래로만 이동할 수 있습니다.

• 아래로만 이동하면 역시 경로는 1가지입니다.

• 따라서 dp[i][0] = 1 (모든 i)가 됩니다.

3. 나머지 셀의 경우

• 임의의 셀 (i, j)에 도달하는 경로의 수는,

  바로 위 (i-1, j)에서 오는 경로의 수와 왼쪽 (i, j-1)에서 오는 경로의 수의 합입니다.

• 즉, dp[i][j] = dp[i-1][j] + dp[i][j-1]가 됩니다.

이 문제의 핵심은 셀에 도달할 수 있는 모든 경우의 수를 구하는 것입니다. 직접 그림을 그리면서 생각해보시면 이해가 잘 되실 겁니다.

추가적인 질문이 있다면 편하게 질문 바랍니다.

감사합니다.