[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]보다 작아지게 된다.
그래서 계산에 영향을 주지 않으며 음수값을 없애기 위해
위와 같이 취하였다.