[백준 DP] 10844번 - 쉬운 계단 수

10844번 - 쉬운 계단 수 

 

---

<문제>

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

10844번: 쉬운 계단 수

 

<문제 풀이>

N = 1

1, 2, 3, 4, 5, 6, 7, 8, 9

 

N = 2

10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98

 

N = 3

101, 121, 123, 210, 212, 232, 234, 321, 323, 343, 345, 454, 456, 432, 434, 543, 545, 565, 567, 654, 656, 676, 678, 765, 767, 787, 789, 876, 878, 898, 987, 989 

 

처음에는 1차원 배열로 접근을 해서 규칙을 찾지 못 했습니다. 

이 문제를 풀 때 가장 중요한 부분은 2차원 배열을 선언하는 부분이라고 생각합니다. 몇 자리수의 계단 수를 구하는지 계단수의 마지막 자리 수가 무엇인지를 저장하는 2차원 배열을 사용하면 동적계획법으로 문제를 해결할 수 있습니다. 

그리고 제가 아직도 많이 놓치고 있는 long long...  문제에서 1000000000으로 나눈 나머지를 구하라고 했을 때 long long 자료형부터 생각을 하고 접근 했어야 했는데.. 이것 때문에 '틀렸습니다'를 몇 번이나 본건지...

여하튼 2차원 배열과 long long 자료형을 사용한다는 것만 빠르게 캐치한다면 쉽게 풀 수 있는 문제라고 생각합니다.

점화식 : dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

 

<코드>

#include <iostream>
#define div 1000000000
using namespace std;

int N;
long long dp[101][11] = { 0, };

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

	cin >> N;

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

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j + 1];
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else {
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
			}

			dp[i][j] %= div;
		}
	}

	int output = 0;
	for (int i = 0; i <= 9; i++) {
		output += dp[N][i];
	}

	cout << output % div << endl;

	return 0;
}

 

 

 

2022.11.26