ShaShaKa Dev Note

쉬운 계단 수

21 July 2019

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

이번은 동적 계획법을 이용해 계단 수를 구하는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

#define mod 1000000000

static int dp[101][10] = {};

int main(void) {

	int N;
	
	scanf("%d", &N);

	for (int i = 1; i < 10; i++) {
		dp[1][i] = 1;
	}
	dp[1][0] = 0;

	for (int i = 2; i <= N; i++)
	{
		for (int k = 0; k < 10; k++)
		{
			if (k == 0)
			{
				dp[i][0] = dp[i - 1][1];
			}
			else if (k == 9)
			{
				dp[i][9] = dp[i - 1][8];
			}
			else {
				dp[i][k] = (dp[i - 1][k - 1] + dp[i - 1][k + 1]) % mod;
			}
		}
	}

	int sum = 0;

	for (int i = 0; i < 10; i++)
	{
		sum = (sum + dp[N][i]) % mod;
	}

	printf("%d" , sum );

	return 0;
}

각 자리수마다 1씩 차이나는 수를 만드는 문제이므로 각각 앞자리수에서 만든 개수를 활용해 만들 수 있습니다.
0인 경우는 앞자리수가 1, 9인 경우는 앞자리수가 8, 6인 경우는 앞자리수가 5 혹은 4 처럼 아래와 같은 규칙을 발견할 수 있습니다.
0,9인 경우는 각각 1,8로 만든 가지수와 동일, 1~8인 경우는 각 수에서 1을 빼거나 1을 더한 수의 가지수의 합만큼이 가능합니다.
1,000,000,000으로 나눈 수를 return하므로 int의 최대값이 넘어가지 않게 해당 수마다 나머지를 저장해줍니다.
마지막자리수까지 해당 계산을 연산하고, 0~9까지의 모든 가지수 합을 더해서 return해주도록 합니다.