10844번 쉬운 계단 수

문제 링크 : www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

---

<알고리즘>

   1) 배열을 이용하여 (행=자리수, 열=자리당 i번째 숫자가 올때 계단수의 가짓수) 1자리일때~ N자리일 때까지를 구함

   2) 해당 행열의 값은 열의 index가 첫자리에 왔을때의 경우의 수이기 때문에 최종 결과값을 더할때 0열은 더하지 않는다.

 

 

ex ) N =5 일때의 값을 구한다.

 

1) 1자리 수일때의 경우는 정해져 있기에 미리 초기화 

	0	1	2	3	4	5	6	7	8	9
0
1	1	1	1	1	1	1	1	1	1	1
2
3
4
5

 

2) 2자리 수일 때의 경우는 1자리 수일때 경우 고려해서 계산

   2자리 수의 경우 : 10,12, 21,23, 32,34, 43,45, 54,56, 65,67, 76,78, 87,89, 98

	0	1	2	3	4	5	6	7	8	9
0
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	2	2	2	2	2	2	1
3
4
5

 

3) 3자리 수일 때의 경우는 1자리 수일때 경우 고려해서 계산

   3자리 수의 경우 : 101,121,123, 210,212,232,234, 321,323,343,345, 432,434,454,456, 543,545,565,567, 654,656,676,678, 765,767,787,789, 876,878,898, 987,989

	0	1	2	3	4	5	6	7	8	9
0
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	2	2	2	2	2	2	1
3	2	3	4	4	4	4	4	4	3	2
4
5

 

4) 4자리부터는 직접 작성이 어렵기에 앞의 규칙을 살핀다.

   4-1) 0열은 제일 첫자리로 올 순 없지만 2번째 자리부터 올수 있는데 그때 이전 행의 1열의 경우를 그대로 쓸 수 있기에 이전 행의 1열 값을 입력한다.

   4-2) 1~8열의 경우 자신-1, 자신+1의 경우가 올수 있으므로 이전 행의 자신-1열값, 자신+1열값을 사용

   4-3) 9열의 경우, 자신 뒤에 8만이 올수 있기에 이전 행의 8열 값을 입력한다.

	0	1	2	3	4	5	6	7	8	9
0
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	2	2	2	2	2	2	1
3	2	3	4	4	4	4	4	4	3	2
4	3	6	7	8	8	8	8	7	6	3
5

 

5) 4번 과정을 이어한다.

	0	1	2	3	4	5	6	7	8	9
0
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	2	2	2	2	2	2	1
3	2	3	4	4	4	4	4	4	3	2
4	3	6	7	8	8	8	8	7	6	3
5	6	10	14	15	16	16	15	14	10	6

 

6) 결과 값으로 5번 행의 1~9열까지의 값을 더한다. (0은 첫 자리에 올수 없으므로 제외)

    result : 10+14+15+16+16+15+14+10+6=116

 

 

 

 

 

 

코드 구현 (메모리 : 2016KB    시간 : 0ms)

#include <iostream>
#include <vector>
using namespace std;

int mod = 1000000000;

int main() {
	int N = 0;
	cin >> N;

	int result[101][10] = { 0, };
	int answer = 0;

	result[1][0] = 1;
	for (int j = 1; j < 10; j++) {
		result[1][j] = 1;
	}

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0) {
				result[i][j] = (result[i - 1][j + 1]) % mod;
			}
			else if (j == 9) {
				result[i][j] = (result[i - 1][j - 1]) % mod;
			}
			else {
				result[i][j] = (result[i - 1][j - 1] + result[i - 1][j + 1]) % mod;
			}
		}
	}

	for (int j = 1; j < 10; j++) {
		answer += result[N][j];
		answer %= mod;
	}
	
	cout << answer % mod << "\n";
	return 0;
}

 

 

+) 처음 생각한 오답 코드

#include <iostream>
#include <vector>
using namespace std;
int mod = 1000000000;
int main(){
	int N =0;
    cin>>N;
    
    vector<int> result;
    result.push_back(0);
    result.push_back(9);
    if(N!=1){
    	for(int i = 2; i<=N;i++){
        	result.push_back((result[i-1]*2-(i-1))%mod);
        }
    }
    
    cout << result[N]<<"\n";
}

이 경우 오직 N이 1~4일 경우 까지만 고려해서 만든 점화식이기 때문에 즉, 0과 9일 때의 변수 작용이 제대로 고려되지 않았기에 오차가 발생한다.