백준 10844번 쉬운 계단 수1. 문제https://www.acmicpc.net/problem/10844 어떤 수의 인접한 자리의 차이가 항상 1이면 이를 계단 수라고 한다.문제는 다음과 같다.길이가 N인 계단 수의 개수를 구하시오.단 0으로 시작하는 수는 계단 수가 아니다.2. 처음 떠올릴 수 있는 방법 (완전 탐색)처음에는 이런 방식이 떠오를 수 있다.1자리 숫자 만들기→ 뒤에 숫자를 붙이기→ 인접한 자리 차이가 1인지 확인 예를 들어1 → 10, 122 → 21, 233 → 32, 34 이런 식으로 계속 숫자를 만들어 나가는 방식이다.하지만 이 방식은 문제가 있다.길이가 최대 100이기 때문에 가능한 경우의 수가 거의 10^100수준이 된다.즉 완전탐색은 불가능하다.3. 핵심 아이디어 (DP)숫자..