boj, 백준) 1562. 계단 수( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 개요 계단수는 인접한 모든 자릿수의 차이가 1이 난다. 0부터 9까지 모든 한 자릿수가 자릿수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 찾아보자. 3. 문제 힌트 dp[n][i]라 두고, n을 자릿수, i를 가장 오른쪽의 수라고 가정했을 때는 0~9까지 모두 사용하지 않은 계단 수를 구할 수 있다. 그럼, 0~9까지 다 사용했음을 어떻게 표현하면 좋을까? 상태를 추가하면 좋을것같은데!! 4. 문제 풀이 상태를 추가해보자. (1) dp[n][i][x][y] 처음에 접근한 방식이었..
알고리즘/Dynamic Programming
2020. 5. 6. 22:10