Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 백트래킹으로 합이 S가 되는 P 이후의 N개 소수 찾기

이 문제에서는 세 가지 값, 즉 목표 합 S, 기준이 되는 소수 P, 그리고 필요한 소수의 개수 N이 주어집니다. 우리의 과제는 P보다 크면서 그 합이 정확히 S와 같은 N개의 소수 조합을 모두 찾는 것입니다.

문제 예시

입력: N = 2, P = 5, S = 18
출력: 7 11
설명: 5보다 큰 소수는 7, 11, 13이며,
7 + 11 = 18이므로 7과 11이 조건을 만족합니다.

해결 접근 방법

이 문제를 해결하려면 먼저 P와 S 사이에 존재하는 모든 소수를 구해야 합니다. 그다음, 구한 소수들 중에서 합이 S가 되는 N개의 조합을 찾아야 하는데, 이때 백트래킹(backtracking) 기법을 활용합니다.

백트래킹은 가능한 모든 후보 조합을 재귀적으로 탐색하되, 조건에 맞지 않는 경로는 미리 되돌아가 가지치기를 하는 알고리즘입니다. 각 소수를 선택 집합에 포함해 보고, 다시 제외해 보는 두 가지 경우를 모두 탐색함으로써 합이 S이고 개수가 N인 조합을 효율적으로 찾을 수 있습니다.

알고리즘 단계

  1. P+1부터 S까지의 수 중에서 소수를 모두 찾아 리스트에 저장합니다.
  2. 소수의 개수가 N보다 적으면 답이 존재하지 않으므로 종료합니다.
  3. 백트래킹을 통해 각 소수를 포함하거나 제외하며 재귀적으로 탐색합니다.
  4. 선택된 소수의 합이 S이고 개수가 N이면 해당 조합을 출력합니다.

C++ 구현 코드

아래 프로그램은 위 접근 방식을 실제로 구현한 예시입니다.

예시 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> set;
vector<int> primeNo;
bool isPrimeNumber(int x) {
   int sqroot = sqrt(x);
   bool flag = true;
   if (x == 1)
      return false;
   for (int i = 2; i <= sqroot; i++)
      if (x % i == 0)
         return false;
   return true;
}
void printPrimes() {
   int length = set.size();
   for (int i=0; i<length; i++)
   cout<<set[i]<<"\t";
   cout<<endl;
}
void GeneratePrimeSum(int total, int N, int S, int index) {
   if (total == S && set.size() == N) {
      printPrimes();
      return;
   }
   if (total > S || index == primeNo.size())
   return;
   set.push_back(primeNo[index]);
   GeneratePrimeSum(total+primeNo[index], N, S, index+1);
   set.pop_back();
   GeneratePrimeSum(total, N, S, index+1);
}
void PrimesWithSum(int N, int S, int P) {
   for (int i = P+1; i <=S ; i++) {
      if (isPrimeNumber(i))
      primeNo.push_back(i);
   }
   if (primeNo.size() < N)
   return;
   GeneratePrimeSum(0, N, S, 0);
}
int main() {
   int S = 23, N = 3, P = 3;
   cout<<N<<" Prime numbers greater than "<<P<<" with sum = "<<S<<" are :\n";
   PrimesWithSum(N, S, P);
   return 0;
}

코드 동작 원리

  • isPrimeNumber(): 2부터 √x까지 나누어 떨어지는지 검사하는 시행 나눗셈(trial division) 방식으로 소수 여부를 판별합니다.
  • GeneratePrimeSum(): 현재 인덱스의 소수를 선택 집합에 추가한 경우와 제외한 경우를 각각 재귀 호출하며, 합이 S를 초과하면 즉시 탐색을 중단해 불필요한 연산을 줄입니다.
  • PrimesWithSum(): P+1부터 S까지의 소수를 수집한 뒤, 소수 개수가 N 미만이면 해가 없다고 판단하고 백트래킹 탐색을 시작합니다.

실행 결과

3보다 크고 합이 23인 3개의 소수 :
5   7   11

위 출력에서 볼 수 있듯이, 3보다 큰 소수 중 5 + 7 + 11 = 23을 만족하는 세 개의 소수 조합이 성공적으로 출력됩니다. 이처럼 백트래킹을 활용하면 조건을 만족하는 소수 조합을 체계적이고 효율적으로 찾을 수 있습니다.