백준 11057 : 오르막 수

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

 

dp[i][j] : 수의 길이가 (i+1)일 때, 숫자 j로 시작하는 오르막 수의 갯수입니다.

먼저, 수의 길이가 1인 dp[0][0...9]는 모두 1로 초기화해줍니다.

​

수의 길이가 2일 때,

0 시작하면, 0 + 0~9 -> 10개

1 시작하면, 1 + 1~9 -> 9개

2 시작하면, 2 + 2~9 -> 8개

...

9 시작하면, 9 + 9 -> 1개

dp[1][0...9] == { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 } 이므로, 55개입니다.

​

수의 길이가 3일 때,

0 시작하면, 0 + 00~99 -> 55개

1 시작하면, 1 + 11~99 -> 45개

...

9 시작하면, 9 + 99 -> 1개

dp[2][0...9] === { 55, 45, 36, 28, 21, 15, 10, 6, 3, 1} 이므로, 220개입니다.

​

이를 통해, dp[i][j] = dp[i][j + 1] + dp[i - 1][j] 를 구했습니다.

 

#include <cstdio>
int main() {
	int n, dp[1000][10] = { 1,1,1,1,1,1,1,1,1,1 }, s = 10;
	scanf_s("%d", &n);
	for (int i = 1; i < n; i++) {
		dp[i][9] = 1; // dp[i][0] == s + i - 1
		for (int j = 8; j > 0; j--) {
			dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % 10007;
			s += dp[i][j];
		}
	}
	printf("%d", (s + n - 1) % 10007); // n은 dp[i][9] 값 더해주는 것
}

 

1로 초기화하며 1바이트가 아닌 자료형에 memset을 사용할 때는 0 이외의 숫자를 사용하면 안되는 것을 알았습니다.

memset은 바이트 단위로 초기화하기때문에,

4바이트 int형은 00000001000000010000000100000001처럼 초기화가 됩니다.