[C언어] 백준 10844 : 쉬운 계단 수

생각의 흐름

문제 이해가 되지 않았다.
질문 검색 탭에 가서 어떤 문제인지 대충 파악했다. 코드는 안보고ㅇㅇ
n = 2라고 해보자, 그러면 각 자리수의 차이가 1이면서 길이가 2인, 십의 자리숫자를 구해보니 17이더라 ~ 이런 의미다. 2일때, 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98로 총 17개가 있고, n = 3이면 32개, n = 4이면 61개, n = 5면 116개인 것 까지 알았다.

• 저장할 배열을 만들어야 한다. 이차원배열을 떠올렸다. dp[i][j]를 만들어주자. i값은 길이이다. 최대 n은 100이기에 101을 만들어주었고, j를 어떻게 할까 하고 넘어갔다.

• n = 2일때 10과 12를 예를 들어보자. n = 3이 될때, 10은 101밖에 될 수 없지만, 12는 121, 123으로 2개가 될 수 있다. 같은 논리로 89는 898밖에 될 수 없다. 따라서 0과 9는 예외처리를 해야겠다고 생각했다.

• dp를 저장해야한다. 0과 9를 따로 빼놓았다. 그 이외의 값은 i - 1번째 줄의 j - 1과 j + 1 두개가 될 수 있기에 (12는 123, 121이 된다.) 두개를 더해준다. 이때 여기에서 j는 0 ~ 9로 설정해줘야겠구나 생각했다. 그래야 0과 9를 분리시킬 수 있고, 사잇값 계산이 가능해진다.

• 이제 0과 9의 경우만 계산해주면 된다. 여기서 고민을 많이했는데, 일단 i - 1번째 줄까지는 확정이다. 질문탭에서 힌트를 보니 어차피 0이 될 수 있는 값은 1하나다. 그러기에 1고정. 9도 마찬가지로 8 하나다. 그러기에 8고정. 그리고 출력하면 된다.

• 마지막으로 주의할건, 나머지값 계산을 매 dp마다 모조리 해주어야 한다는 것이다.

#include <stdio.h>
#define mod 1000000000;

int main()
{
	int dp[101][10];
	int i, j, n;
	int sum = 0;
	scanf("%d", &n);
	i = 0;
	while (i <= 9)
	{
		dp[1][i] = 1;
		i++;
	}
	i = 2;
	while (i <= n)
	{
		j = 0;
		while (j <= 9)
		{
			if (j == 0)
			{
				dp[i][j] = dp[i - 1][1] % mod;
			}
			else if (j == 9)
			{
				dp[i][j] = dp[i - 1][8] % mod;
			}
			else
			{
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
			}
			j++;
		}
		i++;
	}
	i = 1;
	while (i <= 9)
	{
		sum = (sum + dp[n][i]) % mod;
		i++;
	}
	printf("%d", sum);
}

다른 사람 코드또한 같은 논리이다.