[동적 계획법 1] [C++] 10844번. 쉬운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

 

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

해결 방법

우선 규칙을 찾을 필요가 있다.

 

길이가 1인 계단의 수는 몇 개가 있을까?

1 2 3 4 5 6 7 8 9

답은 9개

 

그럼 길이가 2인 계단의 수는?

10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 

답은 17개

 

규칙이 보이는가? 보이지 않아도 된다.

(본인도 푸는데 오래걸렸으니... 이 문제 많이 어려웠었다. 점화식을 유도할 규칙을 찾지 못했기 때문이었다...)

 

보기 쉽게 나타내기 위해 표로 설명하겠다.

 

index로 끝나는 수를 저장할 dp를 만들어 준다.

① dp[0][0]은 0으로 끝나는 1자리 수, dp[0][9]는 9로 끝나는 1자리 수가 저장된다.

 

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	1	1	1	1

길이 1 : 0 (0은 길이 1에 포함되지 않지만 dp를 표현하기 위해 서술) / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9

 

② dp[1][0]은 0으로 끝나는 2자리 수, dp[1][9]는 9로 끝나는 2자리 수가 저장된다.

 

0	1	2	3	4	5	6	7	8	9
1	1	2	2	2	2	2	2	2	1

길이 2 : 10 / 21 / 12 32 / 23 43 / 34 54 / 45 65 / 56 76 / 67 87 / 78 98 / 89

 

③ dp[2][0]은 0으로 끝나는 3자리 수, dp[2][9]는 9로 끝나는 3자리 수가 저장된다.

 

0	1	2	3	4	5	6	7	8	9
1	1	2	2	2	2	2	2	2	1

길이 3 : 210 / 101 121 321 / 212 232 432 / ... / 678 878 878 / 789 989

 

규칙이 보이지 않는가?

 

i의 j 값의 경우 i-1의 j-1과 j+1이 사용되는 것을 볼 수 있다.

예를 들어 i[2][8]이면 8로 끝나는 3자리 수인데 i[1][7]의 67, 87 과 i[1][9]의 89 뒤에 8이 붙어서

678, 878, 898이 되는 것을 볼 수 있다.

 

따라서 점화식은 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이다.

하지만 dp[i][0]과 dp[i][9]인 경우를 주의깊게 살펴볼 필요가 있다.

위의 점화식을 동일하게 적용하면 배열의 index를 넘어가기 때문에 오류가 발생한다.

즉, 해당 경우에는 다른 점화식이 적용되는 것을 생각할 수 있는데 규칙을 찾아보면

dp[i][0]의 경우 dp[i-1][1], dp[i][9]의 경우 dp[i-1][8]과 같다는 것을 볼 수 있다.

 

따라서 최종적인 점화식은

dp[i][j] = dp[i-1][j+1] ( j == 0 )

                dp[i-1][j-1] + dp[i-1][j+1] ( 1 ≤ j ≤ 8 )

                dp[i-1][j-1] ( j == 9 ) 

가 된다.

 

 

해결 과정

위의 점화식으로 코드를 작성하고 문제에서 10억으로 나눠준 나머지를 출력하라고 했으므로 10억으로 나눠준다.

 

최종적인 코드는