[BOJ] 10844번 : 쉬운 계단 수

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 
int d[105][10]; 
const int mod = 1000000000;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 
	for (int i = 1; i <= 9; i++) d[1][i] = 1; 
	
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j > 0) d[i][j] = (d[i][j] + d[i - 1][j - 1]) % mod; 
			if (j < 9) d[i][j] = (d[i][j] + d[i - 1][j + 1]) % mod;
		}
	}
	int result = 0; 
	for (int j = 0; j <= 9; j++) {
		result = (result + d[n][j]) % mod; 
	}
	cout << result << '\n';
}

 

3. solution 2 :

// Authored by : tongnamuu
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/03ae0f4b94fb463f9b0426fad0a82244
#include <bits/stdc++.h>
using namespace std;
long long d[101][10];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= 9; ++i) d[1][i] = 1;
  
  for (int i = 2; i <= n; ++i) {
    for (int k = 0; k <= 9; ++k) {
      if (k != 0) d[i][k] += d[i - 1][k - 1];
      if (k != 9) d[i][k] += d[i - 1][k + 1];
      d[i][k] %= 1000000000;
    }
  }
  long long ans = 0;
  for (int i = 0; i <= 9; ++i) {
    ans += d[n][i];
  }
  ans %= 1000000000;
  cout << ans;
}

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

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