백준코딩일기
-
10844) 쉬운 계단 수 c++백준코딩일기 2021. 2. 4. 20:08
문제 ) www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 ) 이번 문제는 11057 오르막 수와 비슷했다. 1. 0으로 시작하는 수가 없으므로 수의 길이 N = 1 일때, dp[1][1~9] 의 값에 모두 1을 대입한다. 2. 수의 길이 N >= 2 라면 조금 생각이 필요하다. 계단 수란, "인접한 모든 수의 차이가 1"이라고 했다. 3. 그렇다면 두 자리 수에서 0 다음에 올 수 있는 숫자는 뭐가 있을까? 1 밖에 없다. 4. 그럼 9 다음에 올 수 있는 숫자는? 8 밖에 없다. 5. 1~8의 경우에는 다 2개의 수가 올 수 있다. 예를 들어, 1의 경우는 0,2 ..