[BOJ][DP] 11057. 오르막 수

문제 -> https://www.acmicpc.net/problem/11057

이번 문제는 나름 참신하게 문제를 푼 것 같다?..

어떤 누군가가 이렇게 풀이를 한 사람이 있을수도 있겠지만..

========================================

보통 3중 for문으로 일일이 dp값을 다 더하는 반면에, 

나는 연산량을 줄이려고 다른 점화식을 생각해봤다..

dp[i][j] :  i번째 자릿수에서  숫자 j가 만들어낼 수 있는 경우의 수

여기서 만들어 낼 수 있는 경우의 수라고 함은 

숫자 j가 i+1번째 자릿수의 가능한 경우의수를 의미한다.

dp[i][10] : i+1번째 자릿수의 모든 경우의 수

i-1 번째 자릿수의 가능한 경우의 수는 

i번째의 숫자 0이 만들 수 있는 경우의 수와 같으므로 

dp[i][0] = dp[i-1][10]으로 정의하였다.

(단, j > 0) dp[i][j] = dp[i][j-1] - dp[i - 1][j - 1] 과 같다.

dp[i][0] = dp[i-1][10] 이고, dp[i][1] = dp[i][0] - dp[i-1][0]과 같기 때문.

< N = 0일때 >

<N = 1일때>

<N = 2일때>

나의 코드상에 

dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1] + 10007) % 10007; 

이렇게 적혀있는 이유는, 

만약 dp[i][j-1]이 dp[i-1][j-1] 보다 크면서 10007을 넘어버리면

나머지 연산 때문에 dp[i-1][j-1]보다 작아지게 된다.

그래서 계산에 영향을 주지 않으며 음수값을 없애기 위해

위와 같이 취하였다.

소스(Gitihub)