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