먼저 $0 < x_1 < \cdots < x_6$이면서 $x_1 + \cdots + x_6 \le 6M$을 만족하는 경우의 수가 필요합니다.
증가 조건은 다루기 까다롭기 때문에 추가 변수를 도입합니다: $y_i = x_i - x_{i-1} - 1$ (단 $x_0 := 0$).
식을 고쳐 쓰면 $6y_1+5y_2+4y_3+3y_4+2y_5+y_6 \le 6M-21$이 되며, $dp[i][j]: y_{i+1}=\cdots=y_6=0$이면서 해당 부등식을 만족하는 경우의 수로 정의하여 DP로 풀 수 있습니다.

leomessi 1년 전
DP 테이블을 어떻게 잡아야 할 지 갈피를 못 잡고 있는 상황입니다.
물건의 가짓수가 매우 많은 배낭 문제로 생각하고 풀려니 메모리 제한에 걸리는데, 어떻게 해야 실마리를 잡을 수 있을 지 궁금합니다.
감사합니다.