[백준 10844 c++ V] 쉬운 계단 수

문제 링크

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

문제 접근

// [백준 10844 c++ V] 쉬운 계단 수 
// 문제: n 자리의 계단 수의 개수를 1000000000로 나눈 나머지를 구하는 문제
// 접근1: 직접 갯수 세서 개수간의 규칙으로 점화식 찾으려 했으나 못찾음
// 점근2: n-1 의 계단수와 n의 계단수의 규칙 찾으려 함 

문제 풀이

// 풀이: n자리의 1의 자리가 0인 계단수 : n-1자리의 1의 자리수가 0 또는 2인 계단수의 합
// 식으로 표현 1<= L <=8 dp[n][L] = dp[n-1][L-1]+dp[n-1][L+1]
// n의 1의 자리수가 0 일 때는 1 밖에 안됨 : dp[n][0] =dp[n-1][1]
// n의 1의 자리수가 9 일 때는 8 밖에 안됨 : dp[n][9] =dp[n-1][8]
// 이차원 dp 배열에 n 자리의 L로 끝나는 계단 수의 개수 저장

주의

// 주의: dp값이 커서 long long 자료형 써야 됨
// 주의: 출력에 1000000000 으로 나눈 나머지를 출력해야 하는데 dp 과정중에도 1000000000을 나눈 나머지를 저장해야 답 맞음 -> 이해 안감

 

개념

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<deque>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준 10844 c++ V] 쉬운 계단 수 
// 문제: n 자리의 계단 수의 개수를 1000000000로 나눈 나머지를 구하는 문제
// 접근1: 직접 갯수 세서 개수간의 규칙으로 점화식 찾으려 했으나 못찾음
// 점근2: n-1 의 계단수와 n의 계단수의 규칙 찾으려 함 
// 풀이: n자리의 1의 자리가 0인 계단수 : n-1자리의 1의 자리수가 0 또는 2인 계단수의 합
// 식으로 표현 1<= L <=8 dp[n][L] = dp[n-1][L-1]+dp[n-1][L+1]
// n의 1의 자리수가 0 일 때는 1 밖에 안됨 : dp[n][0] =dp[n-1][1]
// n의 1의 자리수가 9 일 때는 8 밖에 안됨 : dp[n][9] =dp[n-1][8]
// 이차원 dp 배열에 n 자리의 L로 끝나는 계단 수의 개수 저장
// 주의: dp값이 커서 long long 자료형 써야 됨
// 주의: 출력에 1000000000 으로 나눈 나머지를 출력해야 하는데 dp 과정중에도 1000000000을 나눈 나머지를 저장해야 답 맞음 -> 이해 안감
// 질문: 출력에 1000000000 으로 나눈 나머지를 출력해야 하는데 dp 과정중에도 1000000000을 나눈 나머지를 저장해야 답 맞음 -> 이해 안감
// 1~9 : 9
// 10 12 21 23 ... 87 89 98 : 17
using namespace std; // cin,cout 편하게 사용 라이브러리 
#define MAX 101

int n;
long long dp[MAX][MAX];
int ar[MAX];

int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);// 입출력 시간 단축
	cin >> n;

	dp[1][0] = 0;
	for (int i = 1; i <= 9; i++) {
		dp[1][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		// dp 점화식
		for (int j = 0; j <= 9; j++) {
			if (j == 0) { dp[i][j] = dp[i - 1][j + 1]%1000000000; }
			else if (j >= 1 && j <= 8) { dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])%1000000000; }
			else if(j == 9){ dp[i][j] = dp[i - 1][j - 1]%1000000000; }
		}
	}
	long long sum = 0;
	for (int i = 0; i <= 9; i++)
	{
		sum += dp[n][i];
	}
	cout << sum%1000000000;

	return 0;
}