이 문제도 dp를 이용하기에 아주 좋은 문제인 것 같다.
https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
전략은 dp테이블을 2차원 배열로 다음과 같이 생성하는 것! dp[자릿수][n으로 끝나는 수]
배열은 0부터 시작하기 떄문에 dp[1][2]는 자릿수가 2개인 숫자 중에 2로 끝나는 수의 개수를 의미한다.
계단 수의 특징은 0과 9로 끝나는 수는 다음 자리수에 1과 8만 올 수 있으므로 해당 케이스는 따로 처리하고,
나머지 숫자들은 자신의 수 보다 +1, -1 한 dp[i][j+1] + dp[i][j-1]로 계산한다.
또한 수의 크기가 크므로 자료형을 long으로 지정해주자
'알고리즘 문제 > 다이나믹 프로그래밍' 카테고리의 다른 글
| [Java] 다이나믹 프로그래밍 (오르막 수) (0) | 2023.09.17 |
|---|---|
| [Java] 다이나믹 프로그래밍 (동전 1) (0) | 2023.06.28 |
| [Java] 다이나믹 프로그래밍 (신나는 함수 실행) (0) | 2023.06.27 |
| [Java] 다이나믹 프로그래밍 (1,2,3 더하기 4) (0) | 2023.02.19 |
| [Java] 다이나믹 프로그래밍 (진우의 달 여행 (Large)) (0) | 2023.02.16 |