[AC] 10844 쉬운 계단 수

출처 : https://www.acmicpc.net/problem/10844

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/10844.cpp

정말 많은 생각을 하게 한 문제이다.

DP인것은 알았으나 어떤식으로 작성해야할지 정말 감이 오지 않았다.

역시 이럴땐 하나씩 다 해보는것이 최고이다.

나는 N이 1부터 3까지 전부 만들어 보았다. 시작값은 0이 될수없으므로 1부터 시작하여 

가장 앞자리가 1, 2, 3...9 까지 전부 구해보았다. (많은 DP문제가 이런식으로 접근한다.)

이렇게 하고나서 규칙을 찾기 위해 많은 시간을 소모했다. 

결국은 삼각형 구조였는데, 나는 삼각형구조를 생각은 했으나 직각삼각형 구조를 생각하여 쉽게 풀리지 않았던것 같다.

개인적인 경험으로 DP에서 이렇게 배열을 조합해야 한다면 결코 어렵게 풀리지 않으며, 특히 수가 나열된상태에서 찾는것이라면 상하좌우대각선포함해서 1칸씩 움직이는 범위안에 규칙이 존재하는것 같다.

뭐 결국은 풀어서 다행이다.