10844번
-
[백준 10844번] 쉬운 계단 수 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 5. 30. 15:16
백준알고리즘 10844번 : 쉬운 계단 수 (Solved.ac 난이도 Silver1) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP(Dynamic programming) 문제이다. 초항의 길이별 정답을 통해 규칙을 찾고, 그 규칙들로 길이 N인 계단 수를 찾을 수 있다. 규칙을 찾기위해 자리 길이가 1일때와 2일때를 계산해보았다. N=1일때 경우의수? 1~9 까지 총 9가지(0으로 시작하는 수는 계단 수가 아님) N=2일 경우의 수? 맨 뒤에 9가 붙는 경우(앞에 8이 있는 갯수) - 1 맨 뒤에 8이 붙는 경우 (앞에 7,9가 있는 갯수) 맨 뒤에 ..