문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
풀이
#include<iostream>
#include<algorithm>
#include<vector>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
int main() {
vector<vector<long>> dp;
int N;
long sum = 0;
cin >> N;
dp.assign(N + 1, vector<long>(10, 0));
for (int i = 1; i < 10; i++)
dp[1][i] = 1;
for (int i = 2; i <= N; i++) {
for (int j = 0; j < 10; 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]) % 1000000000;
}
}
for (int i = 0; i < 10; i++)
sum += dp[N][i];
cout << sum % 1000000000;
}
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준 1931번] 회의실배정 / C++ (0) | 2020.08.23 |
---|---|
[백준 9095번] 1, 2, 3 더하기 / C++ (0) | 2020.08.23 |
[백준 11053번] 가장 긴 증가하는 부분 수열 (0) | 2020.08.20 |
[백준 2667번] 단지번호붙이기 / C++ (0) | 2020.08.19 |
[백준 2012번] 등수 매기기 / C++ (0) | 2020.08.18 |