백준 22115번: 창영이와 커피

https://www.acmicpc.net/problem/22115

22115번: 창영이와 커피

예제) 

4 5
1 1 3 2

들어온 카페인 양을 1 1 2 3으로 정렬 (안해도 될거같긴함)

 

intake

i  \  j	0	1	2	3	4	5
0	0	0	0	0	0	0
1	1	1	1	1	1	1
2	1	2	2	2	2	2
3	0	1	2	3	4	4
4	0	1	2	3	4	5

cnt

i  \  j	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	1	1	1	1	1
2	0	1	2	2	2	2
3	0	1	1	2	3	3
4	0	1	1	1	2	2

 

1~(i-1)번째 커피를 마셔서 얻을 수 있는 카페인(최대 j)의 양을 조사한다.

i번째 커피를 먹을 수 없다면 i-1번째 커피를 먹었을 때의 카페인 양을 선택한다.

i번째 커피를 먹을 수 있다면 i-1번째 커피를 먹었을 때와 비교해서 더 높은 쪽 선택한다.

만약 같은 양의 카페인을 마실 수 있다면, 마신 커피의 양이 더 작은 쪽을 선택한다.

 

#include <bits/stdc++.h>
#define INF 100001
using namespace std;

vector<int> Caffeine;
vector<int> intake[101], cnt[101];
int answer = INF;

void Input(int n) {
  int Ci;
  Caffeine.push_back(0);
  while (n--) {
    cin >> Ci;
    Caffeine.push_back(Ci);
  }
}

void TakeCaffein(int n, int k) {
  for (int i = 0; i <= k; i++) {
    intake[0].push_back(0);
    cnt[0].push_back(0);
  }
  for (int i = 1; i <= n; i++) {
    intake[i].push_back(0);
    cnt[i].push_back(0);
  }
  for (int i = 1; i <= n; i++) {
    int now_caffein = Caffeine[i];
    for (int j = 1; j <= k; j++) {
      if (now_caffein > j) {
        intake[i].push_back(intake[i - 1][j]);
        cnt[i].push_back(cnt[i - 1][j]);
      } else {
        if (intake[i - 1][j] > intake[i - 1][j - now_caffein] + now_caffein) {
          intake[i].push_back(intake[i - 1][j]);
          cnt[i].push_back(cnt[i - 1][j]);
        } else if (intake[i - 1][j] <
                   intake[i - 1][j - now_caffein] + now_caffein) {
          intake[i].push_back(intake[i - 1][j - now_caffein] + now_caffein);
          cnt[i].push_back(cnt[i - 1][j - now_caffein] + 1);
        } else {
          intake[i].push_back(intake[i - 1][j]);
          cnt[i].push_back(min(cnt[i - 1][j], cnt[i - 1][j - now_caffein] + 1));
        }
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, K;
  cin >> N >> K;
  Input(N);
  sort(Caffeine.begin(), Caffeine.end());
  TakeCaffein(N, K);
  for (int i = 1; i <= N; i++) {
    if (intake[i][K] == K) {
      answer = min(answer, cnt[i][K]);
    }
  }

  if (answer == INF)
    cout << "-1";
  else
    cout << answer;
}