leomessi   1년 전

DP 테이블을 어떻게 잡아야 할 지 갈피를 못 잡고 있는 상황입니다.

물건의 가짓수가 매우 많은 배낭 문제로 생각하고 풀려니 메모리 제한에 걸리는데, 어떻게 해야 실마리를 잡을 수 있을 지 궁금합니다.

감사합니다.

zenith82114   1년 전

먼저 $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년 전

@zenith82114 감사합니다. 시도해보겠습니다.

댓글을 작성하려면 로그인해야 합니다.