C++로 코딩 대회에서 목표 점수 G 이상을 얻기 위해 풀어야 하는 최소 문제 수 찾기

문제 개요

코딩 대회에는 난이도별로 점수가 다르게 매겨진 여러 문제가 출제됩니다. i번째 난이도의 한 문제는 100×i점을 가지며, 길이가 D인 배열 p는 각 난이도별 문제 수를 저장합니다. 즉, p[1]부터 p[D]까지의 합이 대회의 전체 문제 수가 됩니다. 또한 배열 c는 특정 난이도의 모든 문제를 완벽히 해결했을 때 추가로 지급되는 보너스 점수를 나타냅니다.

코딩 사이트에서 사용자의 총점(total_score)은 다음 두 가지 요소의 합으로 계산됩니다.

기본 점수: 해결한 모든 문제 점수의 합계
보너스: 100i점짜리 문제를 전부 해결하면 기본 점수 외에 추가 보너스 c[i]를 획득합니다.

대회에 처음 참가한 Amal은 아직 아무 문제도 풀지 않았습니다. 그의 목표는 총점 G점 이상을 달성하는 것이며, 이를 위해 최소 몇 개의 문제를 풀어야 하는지 구하는 것이 우리의 과제입니다.

예를 들어 입력이 G = 500, P = [3, 5], C = [500, 800]이라면 출력은 3입니다.

풀이 접근 방식

이 문제는 비트마스크(bitmask) 완전 탐색으로 해결할 수 있습니다. 난이도의 수 D가 최대 10으로 제한되므로, 2^D가지 조합을 모두 확인해도 충분히 빠른 시간 안에 처리할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

각 비트 조합은 "어떤 난이도의 문제를 전부 풀어서 보너스까지 챙길 것인가"를 의미합니다.
선택된 난이도는 해당 난이도의 모든 문제 점수와 보너스 점수를 함께 합산합니다.
그래도 목표 점수 G에 미치지 못하면, 선택하지 않은 난이도 중 가장 높은 것에서 필요한 만큼의 문제를 추가로 풉니다(그리디 방식).
목표 점수를 달성한 경우, 푼 문제 수의 최솟값을 갱신합니다.

위 절차를 의사 코드로 표현하면 다음과 같습니다.

D := p의 크기
mi := 10000   // 최소 문제 수 초기값
for i := 0 부터 (1 << D) - 1 까지 반복:
   sum := 0       // 현재 조합의 총점
   count := 0     // 현재 조합에서 푼 문제 수
   at := 0        // 클리어하지 않은 난이도 인덱스
   b := i의 비트 값으로 초기화한 10비트 배열
   for j := 0 부터 D-1 까지 반복:
      if b의 j번째 비트가 1이면:          // 해당 난이도를 완전히 클리어
         count := count + p[j]
         sum := sum + (j + 1) * 100 * p[j] + c[j]   // 기본 점수 + 보너스
      else:
         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) * 100 * d
         count := count + d
   if sum >= G then:
      mi := min(mi, count)
return mi

C++ 구현 예시

아래 구현을 통해 더 자세히 이해해 봅시다.

#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 }

출력

결과 분석

출력이 3이 되는 이유를 살펴보겠습니다. 첫 번째 방법은 200점짜리 문제 3개를 풀어 기본 점수 600점으로 목표를 달성하는 것이고, 두 번째 방법은 100점짜리 문제 3개를 모두 풀어 기본 점수 300점에 보너스 500점을 합친 총 800점을 확보하는 것입니다. 두 개 이하의 문제로는 500점을 넘길 수 없으므로, 필요한 최소 문제 수는 3이 됩니다.