쉬운 계단의 수
-
(백준 10844번 쉬운 계단의 수 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 8PROGRAMMING/알고리즘 2024. 3. 14. 08:16
출근 전 한문제 컷! 이라고 말하기엔 그제부터 풀었던 쉬운 계단의 수 문제 ㅎㅎ 백준 10844번 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이는 간단하다!(라고 말하고 생각하는데 하루 걸렸다) f(n)을 n자리 계단수의 갯수라고 정의하면 f(n+1) = 2 * f(n) - {n자리 계단수 중 마지막 자리가 0또는 9인 수의 갯수}로 나타낼 수 있다. 마지막 자리가 0 또는 9인 수를 알기 위해 DP[n][10]을 만들어 기록해주기만 하면 완성! 마지막 자리수가 1인 수만이 그 다음 숫자의 마지막 수를 0으로 만들 수 있고, 마지막 자리수가 8인 수만..