2019년 01월 17일
yoonyoung

백준 10844번 문제 : 쉬운 계단 수

이 문제는 n을 입력받아 길이가 n인 계단 수를 출력하는 문제이다. 계단 수란 45656처럼 인접한 모든 자리수의 차이가 1이 나는 수를 말한다. Dynamic Programming으로 풀 수 있는 문제이고, 나는 bottom-up 방식으로 풀었다. 처음부터 답을 구해 보니, 다음과 같은 점화식을 얻을 수 있었다.

d[n][m] = d[n-1][m-1] + d[n-1][m+1]

단, m이 0일 때는 m-1이 마이너스가 되어버리고, 9일 때는 m+1이 10이 되어버리므로 조건을 걸어 처리해주어야 한다. 점화식을 구해 구현을 다 한 와중에도 무려 6번이나 틀렸는데, 이유는 자료형 때문이었다. d배열도, 결과값을 저장하는 result값도, result를 리턴하는 함수의 자료형도 모두 long 이상의 자료형을 사용했어야 했다.

#include <iostream>
using namespace std;

long D[101][11];

long go(int n) {
	long result = 0;
	if (n == 0) return 0;
	for (int i = 1; i <= 9; i++) {
		D[1][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j - 1 >= 0) D[i][j] += D[i - 1][j - 1] % 1000000000;
			if (j + 1 <= 9) D[i][j] += D[i - 1][j + 1] % 1000000000; 
		}
	}
	for (int i = 0; i <= 9; i++) {
		result += D[n][i] % 1000000000;
	}
	return result;
}
int main()
{
	int N;
	cin >> N;
	cout << go(N)%1000000000 << endl;
    return 0;
}

← → Top