[BOJ] C++ 10844 쉬운 계단 수 - DP 테이블링 연습하기

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 분석해 보면 자릿수별로 테이블링을 해서 전의 항을 사용할 수 있을 것 같다. 일단 dp로 잡고 테이블링도 dp [k]를 k자릿수에서의 계단 수라고 설정한 뒤 점화식을 구해봤다. 분명 아래 사진처럼 k-1 자릿수를 k 자릿수 구할 때 사용할 수 있긴 한데 특이 케이스를 고려해줘야 했다. k의 값에 따라서 특수 케이스의 계단수가 달라지는 건 확실한데 그 규칙을 정확하게 파악하기 힘들어서 간단하게 다차원 배열을 사용했다. dp [i][j]를 i자릿수에 대해 j로 시작하는 계단수로 설정하니 점화식이 보였다. j==0이면 dp [i][0] = dp [i-1][1] j==9면 dp..

2023.12.18