BOJ 2291 Sequence

<BOJ 2248 이진수 찾기> 문제와 비슷한 다이나믹 프로그래밍 문제이다.
a1<=a2<=a3<=...<=aN이면서 a1+a2+a3+...+aN==M을 만족하는 수열 중 사전 순으로 k번째 수열을 구하는 문제인데, 막연하다. 어려워 보인다. 일단 문제의 조건을 만족하는 수열 aN의 합이 M인 경우의 수를 구하는 것은 좀 더 나아 보인다.
d[val][sum][idx] = 수열 val이상 값 부터 사용해서(이전 값들은 val이하의 값들) 남은 sum을 만드는 경우의 수, idx는 사용하는 수열의 인덱스(길이를 나타내는 것으로 봐도 됨)
로 놓으면 d[val][sum][idx]=SUM(a[idx]=val이상의 수,  d[a[idx]][sum-a[idx]][idx+1] ) 가 될 것 같다. 이렇게 경우의 수를 구했다면, k를 가지고 d[1][sum], d[2][sum]... 들이 저장하고 있는 개수와 비교를 해서 그 때 그 때 해당하는 a[idx]를 출력하면 k번째 수열을 알 수 있을 것이다.

구현해 보려고 하는데, 배열의 크기에서 a[idx]값을 어디까지 잡아야 하는지 잠깐 고민했다. sum값까지 즉 최대 M으로 잡으면 된다! M을 넘을 수는 없기 때문에...

일단 우여곡절 끝에 AC를 받긴 했는데... 자고 일어나서 다시 한 번 보고 다시 풀어봐야겠다.
그리고 다른 사람들 풀이도 봐서 연습하자. 좀 까다롭다.