백준 알고리즘 10844번: 쉬운 계단 수 [C++]

문제 출처: www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

1. 코드

#include <iostream>
#define MIN 1000000000

using namespace std;

int main(void)
{
	int n, sum = 0;
	int dp[101][10] = { 0, };
	cin >> n;
	for (int i = 0; i < 10; i++)
		dp[1][i] = 1;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (j == 0) dp[i][0] = dp[i - 1][1] % MIN;        //수가 0일 경우
			else if (j == 9) dp[i][9] = dp[i - 1][8] % MIN;   //수가 9일 겨우
			else dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j - 1]) % MIN;    //수가 1~8일 경우
		}
	}
	for (int i = 1; i < 10; i++)
		sum = (sum + dp[n][i]) % MIN;
	cout << sum;
	return 0;
}

(실행)

2. 풀이

우선은 문제에 대해 먼저 자세하게 알아보자. 1차이가 나면서 입력한 N만큼 차이가 나야한다고 하는데 1을 입력했을 때는 9가 나오는데 이 말은 1을 입력했을 때는 계단 수를 세지않고 그저 1의 자리수가 몇 개가 존재한지 센 것이고, 2를 입력했을 때는 아래 그림과 같다.

N = 2일 때 계단 수의 종류

N = 2일 때 계단수를 보면 자기 자신에서 1뺀 값과 1더한 값으로 구성이 되어있고, 9만 9 - 1인 8만 가지고 있다. 이것을 식으로 바꾼다면 dp[N] = dp[N - 1] + dp[N + 1]이다.

(왼) N = 2일 떄 첫 번째 수가 2일 경우, (오) N = 3일 떄 첫 번째 수가 2일 경우

그런데 N은 입력한 만큼 수의 길이가 늘어나게 되는데 오른쪽을 보면 2다음에 2자리일 때 1과 3으로 시작하는 경우가 나오기 때문에 이를 조금 더 편하게 구현하기 위해서는 2차원배열로 구현하면 많이 쉬워진다. 이차원 배열로 1열에는 입력한 N의 크기 그리고 2열에는 0~9의 경우의 갯수를 저장하도록 한다고 하면 dp[ i ] [ j ] = dp[ i - 1][ j - 1] + dp[ i - 1 ][ j - 1 ]이 된다.

그리고 여기서 0일 경우가 만약 나온다면 더 이상 줄어들면 -에 도달하기 때문에 무조건적으로 +1이 되는 조건만 추가를 해주고 9일 경우도 더이상 커질 수 없기 때문에 -1이되어 8일 경우에만 접근하도록 조건을 추가해주면 해당 문제를 해결할 수 있을 것이다.

3. 느낀 점

이 문제를 해결할 규칙을 찾았는데 점차 증가하는 방식에 대해 상향식으로 풀게되면 어떻게 해결해야할지 전혀 감이 안잡혀서 결국 다른 사람들이 올린 코드를 봤는데 2차원 배열 통해서 구분을 해놓을 거라고는 정말 상상도 못했다. 아직도 많이 미숙한 것 같다. 정진해야겠다.