일단 문제가 DP로 풀어야 함을 알아내기 위해서는 다음과 같은 조건이 만족하는지를 확인해야 한다. > state가 독립적인가(분할 정복이 가능한가)? 가장 최적의 해를 구하여야 하는가? 여기서는 각 노드의 state가 얼리어답터인지 아닌지 2개로 둘은 서로 명확히 구분되어있다. 따라서 각 노드에 대해 얼리어답터인 경우/아닌 경우 최소 얼리어답터 개수를 파악하고 Bottom-up 방식으로 풀면 해결되는 문제였다. 나는 DP를 재귀를 사용해서 풀었는데, Pypy로 계속 제출하다 메모리초과로 막혀서 알고봤더니 Python3에 sys.setrecursionlimit(10**9)를 넣으면 통과되는 것이었다. 파이썬으로 재귀는 웬만해선 피하고, 어쩔 수 없이 썼다면 문제 조건이 불안할 때 recursion limit을 설정하고 python으로 제출하는 습관을 길러야겠다. (마음 편하게 C/C++을 쓰는 것도 방법인듯 하다) 문제 https://www.acmicpc.net/

쉬운 계단 수 -- 먼저 모든 가짓수를 세는 방법은 다음과 같다. 각 숫자의 가짓수를 파악하면서 진행해본다. 초기는 0 제외 모두 1, 0은 0이다.이다. 0123456789 0111111111 다음으로 넘어가면 0123456789 1122222221 그 다음은 0123456789 1334444432 최종 출력을 구하기 위해서는 각 가짓수 아래의 수를 모두 더하면 된다. 쉬운 계단 수 문제의 해답이다. 계단 수 -- 근데 이번 문제는 0~9까지의 모든 수가 등장하는 계단 수의 개수를 구해야 한다. 따라서, 해당 계단 수가 어떤 숫자들을 포함하고 있는지도 구분을 해야 한다. 0~9까지의 숫자를 모두 고려할 경우 1024가지의 경우가 나오는데, 비트마스킹 기법을 활용하여 공간을 절약하면 TLE나 MLE 없이 AC받을 수 있다. 즉 쉬운 계단수 문제에서 차원을 한 단계 확장하고, 비트마스킹을 사용하여