[C++]백준 - 10844번 문제

10844번: 쉬운 계단 수 (acmicpc.net)

10844번: 쉬운 계단 수

 

10844번 : 쉬운 계단 수

---

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

입력

---

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

 

출력

---

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

 

---

 

생각해 볼 점

---

계단 수를 만들어봅시다.

 

1. 0으로 시작할 수는 없으니 처음엔 1~9 중 하나의 숫자를 택합니다.

2. 이제 왼쪽부터 각 자리 숫자를 x(n)이라고 합시다. (예: 123의 x(1) = 2)

3. 계단 수의 성질에 따라 x(n) = x(n-1) - 1 또는 x(n) = x(n-1) + 1입니다.

4. 이 때, 0이나 9는 각각 더 작거나 큰 수가 없으므로 무조건 2와 8을 택해야 합니다.

 

이제, 모든 경우의 수를 동적계획법을 이용해 저장하여 모든 경우의 수를 구하면 됩니다.

 

단, 출력 형식에 맞추어 연산마다 1,000,000,000의 나머지 연산을 수행합니다.

 

코드

---

#include <iostream>
using namespace std;
int dp[100][10] = {0,}; 	//0 ~ 9까지를 택했을 경우

int solution(int N, int now)	//now = 현재 택하려는 숫자 (0 ~ 9) 
{
    if(N == 0) return 1;
    if(dp[N][now] != 0) return dp[N][now];
    int ret = 0;
    if(0 < now) ret += solution(N-1, now - 1);
    if(now < 9) ret += solution(N-1, now + 1);
    dp[N][now] = ret % 1000000000;
    return dp[N][now];
}

int main() 
{
	int N;
	cin >> N;
	int result = 0;
	for(int i = 1; i < 10; i++) //시작 수는 0을 택할 수 없음 (1 ~ 9)
	{
	    result += solution(N - 1, i);
	    result %= 1000000000;
	}
	cout << result;
	return 0;
}

 

그 외

---

마지막에 for문에서 나머지 연산을 하는 것을 깜빡해서 틀렸습니다.

앞으로 이런 실수에 주의를 기울이도록 해야겠습니다.