๐ฃ ๋ฌธ์ ์ดํด
1. 45656 ๊ณผ ๊ฐ์ด ๋ชจ๋ ์๋ฆฌ ์๊ฐ ์ธ์ ํ ์๋ฆฌ ์์ 1 ์ฐจ์ด๋ ๋, ๊ทธ ์๋ฅผ ๊ณ๋จ ์ ๋ผ๊ณ ํ๋ค.
2. ์ ๋ ฅ์ผ๋ก 1~100 ์ฌ์ด์ ์์ฐ์ N ์ด ์ฃผ์ด์ง๋ค.
3. N ์๋ฆฌ ์์ฐ์ ์ค ๊ณ๋จ ์๊ฐ ์ด ๋ช ๊ฐ์ธ์ง ์ฐพ์ ์ถ๋ ฅํ๋ฉด ๋๋ค.
๋์ ๊ณํ๋ฒ(Dynamic Programming) ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
๐ญ ํ์ด ๊ณผ์
N = 1 ์ธ ๊ฒฝ์ฐ, 1, 2, 3, 4, 5, 6, 7, 8, 9 ๊ฐ ๊ฐ๋ฅํ๋ค.
๋ฌธ์ ์ ์ ์๋ ์กฐ๊ฑด์ ๋ฐ๋ผ 0์ ๋ถ๊ฐํ๋ค.
N = 2 ์ธ ๊ฒฝ์ฐ, 10, 12, 21, 23, 32, 34, .... 98 ๊ฐ ๊ฐ๋ฅํ๋ค.
1 ~ 9 ์ฌ์ด ์๋ฅผ ์ญ์ ์๋ฆฌ๋ก ํ์ฌ ์ผ์ ์๋ฆฌ๋ -1 ํ ์ ๋๋ +1 ํ ์๋ผ๋ ๊ฒ์ ์ ์ ์๋ค.
์ ํ์์ผ๋ก ์ ๋ฆฌํ์๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
dp[i][j] = dp[i+1][j-1] + dp[i+1][j+1]
i ๋ ์๋ฆฌ์ N ์ ๋ปํ๋ dp ๋ฐฐ์ด์ ํ์ด๊ณ j ๋ ๊ทธ ์์ ๊ฐ์ฅ ์ฐ์ธก์ ์์นํ ์ 1~9 ์ด๋ค.
๊ทธ๋ฌ๋, i ๊ฐ 0 ์ธ ๊ฒฝ์ฐ๋ dp[i+1][j+1] ๋ง ๊ณ ๋ คํ๋ฉฐ i ๊ฐ 9 ์ธ ๊ฒฝ์ฐ๋ dp[i+1][j-1] ๋ง ๊ณ ๋ คํ๋ค.
0 ์ธ ๊ฒฝ์ฐ, -1 ์ ์กด์ฌํ์ง ์์ผ๋ฏ๋ก 10 ๋ง ๊ฐ๋ฅํ๊ธฐ ๋๋ฌธ์ด๊ณ
9 ์ธ ๊ฒฝ์ฐ, ๊ทธ ์ด์์ ์กด์ฌํ์ง ์์ผ๋ฏ๋ก 89 ๋ง ๊ฐ๋ฅํ๊ธฐ ๋๋ฌธ์ด๋ค.
์์ฑ ์ธ์ด: C++
#include <cstdio> // c ํ์ค์
์ถ๋ ฅ
#include <algorithm> // std::fill_n
#define mod 1000000000
int dp[110][10] = {0, };
int sumOfStairs(int index){
int sum = 0;
for (int i = 2; i <= index; ++i) {
for (int j = 0; j <= 9; ++j) {
if (j == 0){
dp[i][j] = dp[i-1][j+1];
}else if (j == 9){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
}
}
}
// ์
๋ ฅ์ผ๋ก ๋ฐ์ N ์๋ฆฌ ๊ณ๋จ์์ ์ดํฉ ๊ตฌํ๊ธฐ
for (int i = 1; i < 10; ++i) {
sum = (sum + dp[index][i]) % mod;
}
return sum;
}
int main(){
int nNumber;
scanf("%d", &nNumber);
// ํ์๋ฆฌ ์ซ์๋ฅผ ๋ปํ๋ 1๋ฒ ํ์ ๋ชจ๋ ์์๋ฅผ 1๋ก ์ด๊ธฐํ
std::fill_n(dp[0]+10, 10, 1);
printf("%d\n", sumOfStairs(nNumber));
return 0;
}
๐ ๋ฐฐ์ด ์
DP ๋ฌธ์ ํ์ด๋ฅผ ํ๋ฉด์ ํน์ ๊ฐ์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ผ๋ ๋ฌธ์ ๊ฐ ๋ง์ด ๋ณด์ด๊ธฐ ์์ํ๋ค.
๋ชจ ๋ธ๋ก๊ทธ๋ฅผ ์ฐธ๊ณ ํ์ฌ ๊ธ์ด์จ ์์ด๋ค. (A + B) % M = (A % M + B % M) % M
๋ง์ง๋ง์ ํน์ ๊ฐ์ ํฉ์ ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํด์ผํ๋ค๋ฉด, ๊ณ์ฐ ๊ณผ์ ๋์ค์ ๋๋์ด๋ ๋๋ค๋ ๋ป์ด๋ค.
๊ฐ์ด ๋๋ฌด ์ปค์ ์ค๋ฒํ๋ก์ฐ๊ฐ ๋ฐ์ํ ๊ฒ ๊ฐ๋ค๋ฉด, ๊ทธ๋๊ทธ๋ ๋๋์ด์ฃผ๊ณ ๋ค ๋ํ ๊ฐ์ ์ต์ข ์ ์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํด๋ ๋๋ค๋ ๊ฒ์ด๋ค.