728x90
반응형
https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
쉬운 계단 수 성공분류
시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 | 256 MB | 61191 | 18409 | 13252 | 28.313% |
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
const long long mod = 1000000000;
int N; cin >> N;
vector<int> v(10, 1);
v[0] = 0;
vector<vector<int>>d;
d.push_back(v);
// 한자리수
for (int i = 1; i < N; i++) {
vector<int> v2(10,0);
for (int j = 0; j < 10; j++) {
if (j != 0) {
v2[j] += d[i - 1][j - 1];
}
if (j != 9) {
v2[j] += d[i - 1][j + 1];
}
v2[j] %= mod;
}
d.push_back(v2);
}
long long sum = 0;
for (auto& i : d[N - 1]) {
//cout << i << endl;
sum += i;
}
cout << sum % mod;
}
며칠동안 포스팅을 못했네요.
각 길이의 계단수는 하나짧은 길이의 계단수로부터 만들 수 있다는것을 이용하면 풀수있는문제입니다.
728x90
반응형
'알고리즘 > 백준[C++]' 카테고리의 다른 글
[백준] 단지번호붙이기 C++ (0) | 2021.04.29 |
---|---|
[백준 11048] 이동하기 (0) | 2020.07.31 |
[백준 1010] 다리 놓기 (0) | 2020.07.20 |
[백준 2579] 계단 오르기 (0) | 2020.07.17 |
[백준 1149] RGB 거리 (0) | 2020.07.17 |