[백준/C++]#11057 - 오르막 수

풀이

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int a[1001][1001];
	for (int i=0; i<=9; i++) a[1][i]=1; // 0~9에 1 저장
	for (int i=2; i<=n; i++) {		//2~n 반복
		for (int j=0; j<=9; j++) {	// 0~9 반복
			a[i][j]=0;	// 초기값 저장
			int k = j;
			while (k+1) {	// 반복문을 통해 이전 값 합함
				a[i][j]+=a[i-1][k--];
				a[i][j] %= 10007;
			}
		}
	}
	long long ans=0;
	for (int i=0; i<=9; i++) ans+=a[n][i];
	ans %= 10007;
	cout << ans;
	return 0;
}

개념

오르막수는 이전 문제인 쉬운 계단수와 아주 유사한 다이나믹 프로그래밍 문제이다. 

n이 2가 될 때 출력이 55가 되든 것처럼, n이 증가함에 따라 값이 매우 커진다.

따라서 자료형 long long을 사용했는데, 변수 ans에 자료형 int를 사용해도 잘 실행된다.

문제의 조건처럼, 10007 값으로 나머지 연산을 해서 그런 것 같다.

---

풀이 

오르막수를 구하기 위해서 이차원 배열을 사용한다. 

a[N][L]=∑a[N-1][k]

     (k : 0~9)

 

쉬운 계단수는 if로 나누는 과정이 있었는데, 이번엔 없다.

그 대신, k의 값에 따라 이전 배열 값을 더해야하므로, 반복문을 한번 더 사용해야한다.

for문을 사용하는게 더 깔끔하고 의미를 내포하기 좋지만, while문을 연습겸 사용해보았다.