[백준] No.10164 - 격자상의 경로 (C++)

문제

www.acmicpc.net/problem/10164

10164번: 격자상의 경로

 

풀이

간단한 DP문제로 간단한 점화식

dp[r][c] = dp[r-1][c] + dp[r][c-1] 으로 경로의 수를 계산할 수 있다.

 

k가 0인 경우와 아닌 경우만 나누어 k가 0이 아니라면 두 가지 문제로 분할해서 계산된 값들을 곱해주면 된다.

 

하지만 본인의 경우, 아래와 같은 실수로 애먹었다.

 

경유지인 행, 열 위치 계산을 아래와 같이 진행한다면 큰 오류가 발생한다.

 

int dest_row = k / M +1 , dest_col = k %M; 

 

위와 같은 식은 문제의 예제와 같이

열의 수가 2 이상인 경우

dest_row = 8/5 +1 =  2

dest_col = 8%5 = 3

 

(2,3)의 위치가 알맞게 계산되지만

 

예제 입력이 아래와 같은 경우

5 1 3 

 

이때 경유지인 3번 격자의 행, 열 위치는

dest_row = 3/1 +1 =  4

dest_col = 3%1 = 1

 

으로 잘못된 경우가 발생한다.

 

따라서 단순히 for문을 돌며 순서에 맞는 위치를 계산하는 방법으로 바꾸자 통과했다.

코드