알고리즘 동적계획법 (1) 썸네일형 리스트형 백준 10844 번 - 쉬운계단수 (C++/DP/동적계획법/Dynamic Programming) 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 접근법 동적계획법으로 접근해야 하는 문제이다. 여러가지 예시를 보며 문제부터 파악했다. 자리수를 Y, 맨 뒤 index에 따른 개수를 X로 두고, 2차원 배열을 만들면 cnt[101][10]; 정도로 크기를 두며 이전 값을 참고해 채워나가면 될거같다. 자리수는 2인 것 끝자리 0 -> 10 끝자리 1-> 21 끝자리 2->32,12 끝자리 3->23,43 끝자리 4->34,54 . . . 끝자리 8->78,98 끝자리 9->89 맨 앞자리는 0이 올수 없으므로 위 17가지가 계단수이다. 자리.. 이전 1 다음