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

링크

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

 

 

 

 

문제

---

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

 

 

 

 

입력

---

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

 

 

 

 

출력

---

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

 

 

 

 

예제 입력 1

---

1

 

 

 

예제 출력 1

---

9

 

 

 

 

예제 입력 2

---

2

 

 

 

 

예제 출력 2

---

17

 

 

 

 

 

아이디어 스케치

---

• 앞자리가 0 또는 9를 제외한 1~8사이의 값인 경우에는 (앞자리+1) or (앞자리-1) 두 개의 경우의 수로 나누어진다.
• 맨 앞자리가 0인 경우에는 모든 경우를 제외한다.
• 앞자리가 0인 경우에는 뒷자리가 1만 가능하므로 경우의 수가 1개 존재한다.
• 앞자리가 9인 경우에는 뒷자리가 8만 가능하므로 경우의 수가 1개 존재한다.

 

 

 

 

코드 분할 설명

---

for (int i = 1; i < 10; i++)	// 자릿수가 하나일때는 0을제외한 1~9는 경우의 수가 1가지씩 존재
    dp[1][i] = 1;

for (int i = 2; i <= N; i++) {
    for (int j = 0; j < 10; j++) {
        if (j == 0)		// 앞의 수가 0일 때
            dp[i][j] = dp[i - 1][1];
        else if (j == 9)	// 앞의 수가 9일 때
            dp[i][j] = dp[i - 1][8];
        else     // 그 외
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
    }
}

• 자릿수가 하나일 때는 각 자리별로 경우의 수가 1씩 존재하므로 1로 초기화 해준다.
• 앞의 수가 0일 때는 1만 가능하므로 dp[i-1][1] 을 대입한다.
• 앞의 수가 9일 때는 8만 가능하므로 dp[i-1][8] 을 대입한다.
• 그 외의 상황에서는 dp[i-1][j-1] + dp[i-1][j+1]을 대입한다.

 

 

 

 

전체 코드

---

#include <stdio.h>

int main()
{
	int N;
	int dp[101][10] = { 0, };	// 동적계획법에 사용할 dp테이블
	int sum = 0;

	scanf("%d", &N);	// 자릿수(N)을 입력받음

	for (int i = 1; i < 10; i++)	// 자릿수가 하나일때는 0을제외한 1~9는 경우의 수가 1가지씩 존재
		dp[1][i] = 1;

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0)		// 앞의 수가 0일 때
				dp[i][j] = dp[i - 1][1];
			else if (j == 9)	// 앞의 수가 9일 때
				dp[i][j] = dp[i - 1][8];
			else     // 그 외
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
		}
	}

	for (int i = 0; i <= 9; i++)
		sum = (sum + dp[N][i]) % 1000000000;	

	printf("%d", sum);		// 결과 출력

	return 0;
}

 

 

 

 

제출 결과

---