쉬운 계단 수 - (Dynamic programming - 동적계획법) ★★☆

이번 문제는 어떻게 문제를 풀어나갈지 고민하는데에 시간을 조금 썼다.

각 자리수마다 0 ~ 9 (맨 앞자리는 1~9)의 값을 가질 수 있으므로 2차원 배열을 사용하여 [10][101]배열을 만들었다.

[i][j]에서 j는 자리수를 의미하고 i는 위에서 처럼 숫자를 의미한다.

[][1]은 1~9의 값을 가질 수 있으므로 [1][1]~[9][1]까지는 1을 넣는다. (경우의 수를 의미)

for문을 통하여 첫번째 자리수가 1일 경우 0,2가 2번째 올 수 있으므로 [0][2],[1][2]에 [1][1]을 각각 더해준다.

첫번째 자리가 2일 경우 ... 9일 경우까지 마치면, 2번째 자리수 [0][2]~[9][2]에 숫자가 들어가게 되는데 이는

두번째 숫자가 0~9 일 경우의 각각의 경우의 수를 나타낸다.

 

따라서 n번째 숫자까지 이 과정을 거치고 [0][n]~[9][n] 구간의 값을 더하면 계단수의 총 가지 수가 나오게 된다.