BOJ 5561 - 과자의 분할

BOJ 5561 - 과자의 분할

$dp[i][j]=$ $i$ 개 까지의 과자 중, $i$ 번째 과자를 포함해서 길이 $j$ 를 만들 수 있는 최소 힘

토글링으로 공간복잡도 $O(N)$ 에 풀 수 있다.

총 $i$개에서 길이 $j$를 만든다는 것은 $j$ 나 $i-j$ 를 만들 수 있다는 것이다.

$dp[i-1][j-1]$ 는 $i-1$ 번째 과자를 포함해서 $j-1$ 개의 조각을 만든 것이므로 $i$ 번째 과자를 그대로 붙여주어서 $dp[i][j]=dp[i-1][j-1]$ 로 해주어도 문제없다.

근데 $i-1$ 번째 조각을 포함해서 $j-1$ 개를 만든 것 말고 $i-1$ 번째 조각을 포함하지 않고 $j-1$ 개를 만든 것의 최소힘은 $dp[i-1][i-j]$ 이다.

왜냐면 길이 $i-1$ 에서 $j-1$ 개를 만든다는 것은 $i-j$ 개를 만들 수도 있다는 것을 의미하기 때문이다.

따라서

$$ \begin{aligned} dp[i][j]=Max\begin{cases} dp[i-1][j-1]&(j \ne 1)\\ dp[i-1][i-j]+a[i-1]&(j \ne 1)\\ a[i-1] &(j=1) \end{cases} \end{aligned} $$

$j=1$ 일 땐, $i$ 를 포함하여 $1$ 개의 과자를 얻는데 필요한 최소 힘이므로 무조건 $a[i-1]$ 이다.

$i=1$ 이면 $a[i-1]$ 이 존재하지 않기 때문에 구현상 처리할 필요 없다.

void solve() {  
   int n;  
   cin >> n;  
   vvi dp(2, vi(n + 1));  
   for (int i = 2; i <= n; i++) {  
      int I = i & 1, J = I ^ 1;  
      int x;  
      cin >> x;  
      for (int j = i; j > 1; j--) {  
         dp[I][j] = min(dp[J][j - 1], dp[J][i - j] + x);  
      }  
      dp[I][1] = x;  
   }  
   cout << dp[0][n / 2];  
}