[BOJ] 11057번 : 오르막 수

1. problem : 

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 
int d[1003][10];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 
	for (int i = 1; i <= n; i++) {
		d[i][0] = 1; 
		for (int j = 1; j < 10; j++) {
			d[i][j] = (d[i][j - 1] + d[i - 1][j]) % 10007;
		}
	}
	cout << accumulate(d[n], d[n] + 10, 0) % 10007 << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/11057.cpp

basic-algo-lecture/0x10/solutions/11057.cpp at master · encrypted-def/basic-algo-lecture

dp를 이용해 풀어야 한다. 따라서 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d [i][j]는 i번째 자릿수 중 j로 끝나는 가짓수를 저장한다. 

2. 점화식을 정의한다. d [i][j] = d [i][j-1] + d [i-1][j]로 정의한다. 

3. 초기값을 설정한다. d [i][0] = 1 

점화식은 이렇게 해석해 볼 수 있다. d [i][j-1]에 해당하는 케이스라면 d [i][j]에도 해당한다. 하지만, 이 값만 처리하면 모든 경우를 체크하지 못하게 된다. 예를 들어, d [2][9]에서 d [2][8]만 처리하면, 99는 처리하지 못하게 된다. 따라서, d [i-1]에서 9로 끝나는 경우를 더해주어야 한다.