[백준] 10844번 : 쉬운 계단 수

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 각 자리 계단 수 중에 맨 끝이 0 ~ 9로 끝나는 수의 개수를 2차원 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다.

1) n에 계단 수의 개수를 구하고자 하는 자리 수를 입력받아 저장한다.

2) 2차원 배열 dp를 선언하고, dp[1][1 ~ 9]를 모두 1로 초기화 한다.

• dp[i][j] : i자리 수인 계단 수 중에 맨 끝이 j인 수의 개수
• 1자리 계단 수는 1~9가 존재. 따라서 1자리 계단 수 중 1~9로 끝나는 수의 개수는 각 1개

3) i가 2 ~ n일 때까지 계단 수의 개수를 전부 갱신한다.

• 현재 자리 수의 계단 수는 이전 자리 계단 수 끝에 (이전 자리 계단 수의 끝 자리 수 -1, +1) 해준 수를 붙이는 경우이다.
• ex. 2자리 계단 수를 구한다고 할 때
  • 1의 자리 계단 수 = 1, 2, 3, 4, 5, 6, 7, 8, 9
    • 1의 끝에 (1-1 = 0) 과 (1+1 = 2)를 붙인 수 -> 10, 12
    • 2의 끝에 (2-1 = 1) 과 (2+1 = 3)를 붙인 수 -> 21, 23
    • 3의 끝에 (3-1 = 2) 과 (3+1 = 4)를 붙인 수 -> 32, 34
    • 4의 끝에 (4-1 = 3) 과 (4+1 = 5)를 붙인 수 -> 43, 45
    • 5의 끝에 (5-1 = 4) 과 (5+1 = 6)를 붙인 수 -> 54, 56
    • 6의 끝에 (6-1 = 5) 과 (6+1 = 7)를 붙인 수 -> 65, 67
    • 7의 끝에 (7-1 = 6) 과 (7+1 = 8)를 붙인 수 -> 76, 78
    • 8의 끝에 (8-1 = 7) 과 (8+1 = 9)를 붙인 수 -> 87, 89
    • 9의 끝에 (9-1 = 8)를 붙인 수 -> 98
• 위 과정을 일반화하여 dp를 갱신하면
  • 맨 끝이 0인 자리 수의 개수 = 이전 자리 수 중 1로 끝나는 수의 개수
  • 맨 끝이 9인 자리 수의 개수 = 이전 자리 수 중 8로 끝나는 수의 개수
  • 맨 끝이 j(1~8)인 자리 수의 개수 = 이전 자리 수 중 j - 1, j + 1로 끝나는 수의 개수의 합
• 이를 점화식으로 표현하면
  • dp[i][0] = dp[i - 1][1]
  • dp[i][9] = dp[i - 1][8]
  • (j : 1 ~ 8) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

4) dp[n]에 0 ~ 9로 끝나는 i자리 계단 수들의 개수가 각각 저장되어있으므로 해당 수들을 전부 더하면 n자리 계단 수들의 총 개수를 알 수 있다.

❗계단 수의 개수를 더하는 과정에서 오버플로우가 발생할 수 있기 때문에 dp를 구하는 과정마다 미리 MOD 연산을 해준다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
long long dp[101][10];		// dp[i][j] : i자리 수 계단 수 중에 맨 끝이 j인 수의 개수
const long long MOD = 1000000000;

long long solution() 
{
	// 1자리 계단수는 1 ~ 9 이므로 1 ~ 9로 끝나는 수의 개수는 각 1개씩
	for (int i = 1; i <= 9; i++)
		dp[1][i] = 1;
	
	for (int i = 2; i <= n; i++)
	{
		// 맨 끝이 0인 i자리 수의 개수 = 이전 자리(i - 1) 수 중 1로 끝나는 수의 개수
		dp[i][0] = dp[i - 1][1] % MOD;										
		// 맨 끝이 j(1 ~ 8)인 i자리 수의 개수 = 이전 자리(i - 1) 수 중 (j - 1)로 끝나는 수의 개수 + (j + 1)로 끝나는 수의 개수
		for (int j = 1; j <= 8; j++)
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;			
		// 맨 끝이 9인 i자리 수의 개수 = 이전 자리(i - 1) 수 중 8로 끝나는 수의 개수
		dp[i][9] = dp[i - 1][8] % MOD;		
	}
		
	long long maxValue = 0;
	for (int i = 0; i <= 9; i++)
		maxValue = (maxValue + dp[n][i]) % MOD;
	
	return maxValue;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	cout << solution();
}