본문 바로가기

알고리즘/백준[C++]

[백준 10844] 쉬운 계단 수

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