BaekJoon(10844)::쉬운 계단 수

문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악 여기서 쉬운 계단수란? '인접한 모든 자리의 차이가 1'인 수를 말한다. N이 주어졌을때, 길이가 N인 쉬운 계단 수가 몇개 있는지 구하는 문제이다. 여기서 주의할점은 숫자의 길이가 100자리를 넘는다는 점과 0으로 시작하는 수는 계단수가 아니라는 점이다 문제 풀이 해당 문제의 진행을 다음과 같다. 결국 N자리의 수에서의 계단수의 갯수는 N-1번째 계단의 수에서 결정이 된다. 이유를 잘생각해보면 N자리의 마지막 수는 N-1번째 계단수의 마지막수와 차이가 1일 수 밖에 없기 때문이다. 이러한 점을 잘 생각해보면 다음과 같은 식을 구할 수 있다. 끝자리의 값이 무엇..