[알고리즘][BOJ]11057_오르막 수

BOJ_11057

💡 생각하자

[Dynamic Programming(동적 계획법)의 개발절차]
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기

N=1일 때 0, 1, ⋯, 9까지 총 10개가 존재한다.

N=2일 때 오르막 수를 AB라고 두면, A는 0부터 9까지 가능하다. (0으로 시작할 수 있다는 조건에 의해)
그러면 A=0이고 B는 0~9, A=1이고 B는 1~9, ⋯, A=9이고 B는 9까지 총 55개가 존재한다.

재귀 관계식
DP[i][j] : 길이가 j이고 i로 시작하는 오르막 수의 개수
DP[i][j] = sum(DP[i][j-1] + DP[i+1][j-1] + ⋯ + DP[9][j-1])

💻 구현하자

• 길이가 n인 오르막 수의 개수를 구하는 함수

int calNum(int n) {
	int res = 10; // N = 1

	for (int j = 1;j < n;j++) { // col
		dp[0][j] = res;
		
		for (int i = 1;i <= 9;i++) { // row
			dp[i][j] = (dp[i-1][j] - dp[i - 1][j - 1] + 10007) % 10007;
			res += dp[i][j];
			res %= 10007;
		}
	}

	return res;
}

- 가장 먼저 dp[0][j]는 이전 수행의 결과값으로 갱신한다.

- (A+B+C) % M = (A%M) + (B%M) + (C%M)
- 계산 중 overflow를 방지하기 위해 mod 10007을 해준다.
dp[i][j]를 계산하기 위해 뺄셈을 하는 과정에서, 음수 값이 발생할 수 있으므로 +10007을 해준다.

• 초기 호출문

// init
for (int i = 0;i <= 9;i++) {
	dp[i][0] = 1;
}

printf("%d", calNum(n));

💥 발전하자

• 추가로 공부해야 할 내용

1. 정확하게 어떤 부분에서 mod 연산을 수행해야 하는지 많이 헷갈렸다.

• 에러 및 해결

1. 처음에는 계산 과정에서 음수가 나올 수 있다는 것을 고려하지 못하고 그냥 mod 연산만 해서 이상한 값이 나왔다.

📌 참고하자

나의 코드(Github)