[백준 - 11057] 오르막 수

#include <iostream>
#define MOD 10007
#define ALL 10
using namespace std;
//일차원의 10번째 인덱스는 총합을 의미한다.
long long dp[1001][11] = { 0, };

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 0; i < 10; ++i)
	{
		dp[1][i] = 1;
		dp[1][ALL] += dp[1][i];
	}
	
	for (int i = 2; i <= N; ++i)
	{
		dp[i][ALL] = dp[i][0] = (dp[i - 1][ALL]) % MOD;
		for (int j = 1; j < 10; ++j)
		{
			dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
			dp[i][ALL] = (dp[i][ALL] + dp[i][j]) % MOD;
		}
	}
	
	cout << dp[N][ALL]<< endl;

	return 0;
}

---

||사고 과정

처음에 2까지 경우의 수를 작성해보고

0부터 시작하는 경우의수, 1부터 시작하는 경우의 수 이렇게 나누어 생각을 했던것같다.

 

그렇게 나누어 보다보니까

두자리에서 0으로 시작하는 경우의 수는 한자리의  0 ~ 9로 시작하는 수,

두자리에서 1으로 시작하는 경우의 수는 한자리의  1 ~ 9로 시작하는 수,

...

두자리에서 9으로 시작하는 경우의 수는 한자리의  9로 시작하는 수,

가 나왔다.

 

그래서 자리수를 i, 시작하는 수를 j로 dp[i][j]형태의 이차원 배열로 테이블을 설정했다.

그 후 점화식을 세워보았고

dp[i][0]은 어쩔 수 없이 dp[i - 1][0] + ...  + dp[i - 1][9] 까지 더해주어야했고

dp[i][1]부터는 dp[i][j] = dp[i][j - 1] - dp[i - 1][j - 1] 이라는 식을 쉽게 세울수 있었다.

 

---

||사용 기법

• DP

---

||풀면서 느낀 것

• 테이블설정 후 점화식 작성

역시 DP는 이렇게 푸니까 많이 수월하다.

---

||새로 알게 된것

• MOD 관련

코드부터 예외까지 15분정도로 모두 끝냈지만 MOD 연산 때문에 시간이 많이 소요 됐다. 

MOD연산은 오버프로우(음수)를 막기위해 사용되는 것으로 음수가 나와서는 안되는데

중간에 A = ( A - B ) % MOD 이런 연산이 있는데 A - B에서 이미 음수가 나와 MOD를 해도 의미가 없는 경우가 있었다.

 

그래서 찾은 방법이 MOD를 더해주는것,

A = ( A - B + MOD ) % MOD

---

||나아 진것

• 깔끔한 풀이 사고 였다.