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

백준 10844번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다. 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제는, 45656이란 수가 있다. 이 수를 잘보면 각 자리수마다 1씩 차이나는 것을 알 수 있다. 이런 수를 계단 수라고 한다. 그렇다면 길이가 N개인 계단 수는 몇 개가 나올 수 있는지 구하는 것이 문제이다. 단, 마지막 정답에 1,000,000,000으로 나눈 나머지를 출력한다. 이 문제를 풀면서 주의해야할 점은 0으로 시작하는 숫자는 없다는 것이다. 즉, 0~9까지의 각 자리수가 있지만 첫 자리에는 0이 절대 올 수 없다는 것이다. 그렇다면 DP로 풀기 위해 먼저 첫 자리 수 ..

2020.10.19