갯수 제한이 있는 부분합

n 종류의 수 a[i]가 각각 m[i]개씩 있습니다. 이들 중 몇개를 골라 그 합이 K가 될 수 있는지 판정합시다.

!제약

1 <= n <= 100

1 <= a[i], m[i] <= 100000

1 <= K <= 100000

 

우선 가장 직관적인 점화식을 생각해 본다면 아래와 같은 점화식을 생각할 수 있습니다.

dp[i][j] = i번째 까지의 수를 사용하여 j라는 수를 만들 수 있는가에 대한 불린값

dp[i][j] = dp[i - 1][j - a[i] * k] (j >= a[i] * k && k <= m[i])

 

이러한 점화식으로 답을 구할시에는 시간복잡도가 O(K * sigma(i, m[i])) 가 됩니다.

위의 제약을 고려 했을때 시간내에 문제를 해결할 수 없습니다.

dp를 구현할때 dp의 부분문제에 대한 값들이 boolen값인 경우 이미 호출되어진 부분문제의 값에 대한 중복적인 호출을 초래합니다. 그러므로 우리는 저장되는 부분문제에대한 값을 boolen값이 아닌 다른 값으로 저장할 필요가 있습니다.

 

새롭게 점화식을 셜계해봅시다.

dp[i + 1][j] = i꺄지의 숫자를 사용해서 j를 만들때 i를 사용하고 남은 최대의 갯수

 

위와같은 점화식은 애초에 dp를 -1로 초기화시키고 dp[i + 1][j]의 값을 찾기위해서

i 까지를 사용해서 j를 만들수 있는지 j - i * k 를 만들수 있는지를 전부 확인해볼 필요가 없습니다. 왜냐하면 i - 1까지를 j를 만들때 사용한 i - 1의 남은 갯수의 최대치가 k이면 i까지를 사용해서 j를 만들때 사용하고남은 i의 갯수는 mi이기때문입니다. 그리고 dp[i][j]가 0보다 크면

dp[i + 1][j] = dp[i][j - a[i]] - 1 = d[i][j - a[i] * 2] - 2 = dp[i][j]

이기 때문에 우리는 시간초과를 초래했떤 점화식의 시간복잡도에서 시그마에 해당되는 부분을 제거할수 있습니다. 점화식을 세워보면 아래와 같습니다.

dp[i + 1][j] = mi (dp[i][j] >= 0)

                  -1 (ai > j OR dp[i + 1][j - a[i]] <= 0)

                  dp[i + 1][j - a[i]] - 1(그 외)

이와 같은 점화식으로 문제를 해결할시 시간복잡도는 O(n * k)가 됩니다.

코드는 아래와 같습니다.

 

int dp[n + 1][k + 1];

 

int main(){

  memset(dp, -1, sizeof(dp));

  for(int i = 0; i < k; ++k)

    dp[0][i] = 0;

  for(int i = i; i <= n; ++i)

    for(int j = 0; j <= k; ++j){

      if(dp[i - 1][j] >= 0)

  dp[i][j] = m[i];

else if(a[i] > j || dp[i][j - a[i]] <= 0)

  dp[i][j] = -1;

else

  dp[i][j] = dp[i][j - a[i]] -1;

    }

  if(dp[n][k] > 0) cout << "YES" << endl;

  else   cout << "NO" << endl;

}

 

위의 코드에서 메모리를 절약하기 위해 배열을 재이용 하면 다음과 같은 코드가 된다.

int dp[k + 1];

 

int mian() {

  memset(dp, -1, sizeof(dp));

  dp[0] = 0;

  for(int i = 1; i <= n; ++i)

    for(int j = 0; j <= k; ++j) {

      if(dp[j] >= 0)

  dp[j] = m[i];

      else if(j < a[i] || dp[j - a[i]] <= 0)

        dp[j] = -1;

      else

        dp[j] = dp[j - a[i]] - 1;

    }

  if(dp[k] >= 0)

    cout << "YES" << endl;

  else

    cout << "NO" << endl;

}