10844
-
백준 10844번 쉬운 계단 수 :: 마이구미알고리즘 풀이/동적계획법 2017. 11. 27. 20:33
이 글은 백준 알고리즘 문제 10844번 "쉬운 계단 수" 를 풀이한다.풀이 방법으로는 동적계획법으로 설명한다.문제 링크 - https://www.acmicpc.net/problem/10844 45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 인접한 모든 자리수의 차이가 1인 수를 어떻게 찾을까?직접 적어보면 쉽게 점화식을 만들어낼 수 있다. N = 1=> 1, 2, 3, 4, 5, 6 ......N = 2=> 10, 12, 21, 23, 32, 34, 43, 45 ....