[Baekjoon] 10844번: 쉬운 계단 수

 

 

 

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

---

 

문제 해결 과정

착안

문제에서 말하는 계단수의 특성을 활용하여 동적계획법(dynamic programming)을 통해 계산하고자 하였다. 길이가 $n (n \geq 2)$ 인 계단수를 만들기 위해서는 길이가 $(n-1)$인 계단수의 맨 뒤 자릿수에 숫자 하나를 붙여 새로운 계단수를 만드는 과정을 생각해볼 수 있다. 이때 길이가 $(n-1)$인 계단수의 뒤에 이어붙이는 숫자가

 

• 0인 경우: 길이가 $(n-1)$인 계단수 중, 끝자리가 0인 수의 뒤에만 붙일 수 있다.
• 9인 경우: 길이가 $(n-1)$인 계단수 중, 끝자리가 8인 수의 뒤에만 붙일 수 있다.
• $1 \leq k \leq 8$인 경우: 길이가 $(n-1)$인 계단수 중, 끝자리가 $k-1$이거나 $k+1$인 수의 뒤에 붙일 수 있다.

 

즉, 길이가 $n$ 이며 일의 자릿수가 $k$ 인 계단수의 개수 $f_n(k) \space$ ($n \geq 2$) 는

$$f_n(0) = f_{n-1}(1),$$

$$f_n(9) = f_{n-1}(8),$$

$$f_n(k) = f_{n-1}(k - 1) + f_{n-1}(k + 1). \quad (1 \leq k \leq 8)$$

 

이다.

 

구현

문제에서 정답을 1,000,000,000으로 나눈 나머지를 요구하므로(아마도 int 형의 표현범위를 넘지 않으며 int 형의 변수들을 사용하도록 배려해준 것 같음), 계산 단계별로 나머지 연산을 취하여 오버플로가 발생하지 않도록 주의하여 구현하였다.

 

한편, 0으로 시작하는 계단수는 존재하지 않으므로 가장 처음 길이가 $N=1$ 인 경우에 대해서만 직접 경우의 수를 구하여 초기화해준 다음, 입력받는 $N$ 의 값이 2보다 크거나 같은 경우만 동적계획법을 통해 계산하도록 구현하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Count[10];
int Intermediate[10];

int main()
{
	int N;
	cin >> N;

	N--;
	for (int i = 1; i < 10; i++)
		Count[i] = 1;

	while (N--)
	{
		for (int i = 0; i < 10; i++)
		{
			if (i == 0)
				Intermediate[i] = Count[1];
			else if (i == 9)
				Intermediate[i] = Count[8];
			else
				Intermediate[i] = (Count[i - 1] + Count[i + 1]) % 1000000000;
		}

		for (int i = 0; i < 10; i++)
			Count[i] = Intermediate[i];
	}

	int TotalCount = 0;
	for (int n : Count)
	{
		TotalCount += n;
		TotalCount %= 1000000000;
	}

	cout << TotalCount << "\n";
	return 0;
}

 

실행 결과