C++ 프로그램에서 G 점수를 얻는 데 필요한 점수는 최소한 몇 점인지 찾습니다.

<시간/>

두 개의 배열 p와 c가 각각 D 수의 요소와 또 다른 숫자 G를 갖고 있다고 가정합니다. 코딩 대회에서 각 문제는 난이도에 따른 점수를 가지고 있다고 가정합니다. 문제 p[i]의 점수는 100i입니다. 이 p[1] + ... + p[D] 문제는 경연에 존재하는 모든 문제입니다. 코딩 사이트의 사용자는 total_score라는 숫자를 가지고 있습니다. 사용자의 total_score는 다음 두 요소의 합입니다.

기본 점수 :해결된 모든 문제의 점수 합계
보너스 :사용자가 100i의 점수로 모든 문제를 해결하면 기본 점수를 제외하고 완벽한 보너스 c[i]를 얻습니다.

Amal은 대회에 새로 참가했으며 문제를 해결하지 못했습니다. 그의 목표는 G 이상의 총점을 얻는 것입니다. 우리는 그가 이 목표를 위해 해결해야 하는 문제의 수를 최소한 찾아야 합니다.

따라서 입력이 G =500과 같으면; P =[3, 5]; C =[500, 800]이면 출력은 3

이 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

D := size of p
mi := 10000
for initialize i := 0, when i < 1 << D, update (increase i by 1), do:
sum := 0
count := 0
at := 0
an array to store 10 bits b, initialize from bit value of i
for initialize j := 0, when j < D, update (increase j by 1), do:
   if jth bit in b is 1, then:
      count := p[j]
      sum := sum + ((j + 1) * 100 * p[j] + c[j]
   Otherwise
      at := j
if sum < G, then:
   d := (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100)
   if d <= p[at], then:
      sum := sum + (at + 1)
      count := count + d
if sum >= G, then:
   mi := minimum of mi and count
return mi

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
int solve(int G, vector<int> p, vector<int> c){
   int D = p.size();
   int mi = 10000;
   for (int i = 0; i < 1 << D; i++){
      int sum = 0;
      int count = 0;
      int at = 0;
      bitset<10> b(i);
      for (int j = 0; j < D; j++){
         if (b.test(j)){
            count += p.at(j);
            sum += (j + 1) * 100 * p.at(j) + c.at(j);
         } else {
            at = j;
         }
      }
      if (sum < G){
         int d = (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100);
         if (d <= p.at(at)){
            sum += (at + 1) * 100 * d;
            count += d;
         }
      }
      if (sum >= G) {
         mi = min(mi, count);
      }
   }
   return mi;
}
int main() {
   int G = 500;
   vector<int> P = { 3, 5 };
   vector<int> C = { 500, 800 };
   cout << solve(G, P, C) << endl;
}

입력

500, { 3, 5 }, { 500, 800 }