(1) 248: https://www.acmicpc.net/problem/12013


DP[i][j] = {i 부터 j 까지 수를 합쳤을 때 만들 수 있는 수, 못 만들면 0} 이렇게 정의
그러면 i < j 일 때, DP[i][j] = DP[i][k] != 0 && DP[i][k] == DP[k][j] 이면 DP[i][k] 아니면 0


N^2 을 채우는데 하나 채울 때마다 O(N) 이니까 O(N^3)


(2) 262144: https://www.acmicpc.net/problem/12008


i번째 칸에서 시작해서 어떤 수 k를 만들 수 있는지 생각해보자.


가능성은 두 가지임
1. i번째 칸에 k가 적혀있던가
2. i번째 칸에서 k-1을 만들 수 있고, 거기에서 또다시 k-1을 만들 수 있던가


위 규칙을 이용해서 하나씩 늘려나가면 됨.
입력으로 들어오는 최대값을 M이라 하면 O(N (M + lg N))


소스코드: https://gist.github.com/0xrgb/31d26a3cd5e83131885c94d687f0e376