C++로 짝수·홀수 자릿수 합의 차이가 소수인 범위 내 숫자 개수 구하기

두 수 start와 end가 범위 변수로 주어졌을 때, 이 범위 [start, end] 안에 속하는 숫자 중에서 짝수 위치 자릿수의 합과 홀수 위치 자릿수의 합의 차이가 소수(Prime)가 되는 숫자의 개수를 구하는 것이 목표입니다.

즉, (짝수 위치 자릿수의 합) − (홀수 위치 자릿수의 합)이 소수인 경우를 찾으면 됩니다.

예시로 이해하기

입력 예시 1

start = 230, end = 270

출력: 조건을 만족하는 숫자의 개수: 6개

설명: 230부터 270 사이에서 조건을 만족하는 숫자는 다음과 같습니다.

240 (4 − 2 = 2)
250 (5 − 2 = 3)
251 (5 − 3 = 2)
261 (6 − 3 = 3)
262 (6 − 4 = 2)
270 (7 − 2 = 5)

모든 차이 값이 2, 3, 5로 소수에 해당합니다.

입력 예시 2

start = 1101, end = 1120

출력: 조건을 만족하는 숫자의 개수: 1개

설명: 1101부터 1120 사이에서 조건을 만족하는 숫자는 1120 하나뿐입니다. (3 − 1 = 2, 2는 소수)

문제 해결 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결합니다. 짝수 위치 자릿수의 합과 홀수 위치 자릿수의 합의 차이가 소수가 되는 숫자들의 개수를 배열에 저장해 두고 재사용하는 방식입니다.

사용되는 배열은 arr[size][90][90][2] 형태이며, 여기서 size는 10의 거듭제곱 크기를 의미합니다. 따라서 입력으로 들어올 수 있는 가장 큰 수는 10^size입니다.

재귀 함수 check(int place, int eve, int od, int temp, vector<int> vec)를 호출할 때마다 왼쪽에서 오른쪽으로 0부터 9까지의 자릿수를 배치하며 숫자를 하나씩 만들어 갑니다.

arr[size][x][y][temp]에서 x는 현재까지 배치된 짝수 위치 자릿수의 합, y는 홀수 위치 자릿수의 합을 나타냅니다. 그리고 100 이하의 모든 소수를 미리 저장해 둔 배열 arr_2[]를 사용하여 요구되는 차이 값이 소수인지 판별합니다.

알고리즘 단계

변수 start와 end를 입력받습니다.
전역 배열 arr[size][90][90][2]와 100 이하의 소수를 담은 배열 arr_2[]를 선언합니다.
함수 check()는 현재 자릿수 위치(place), 짝수 위치 자릿수의 합(eve), 홀수 위치 자릿수의 합(od), 경계 상태(temp), 자릿수를 담은 벡터(vec)를 매개변수로 받습니다.
재귀적으로 arr[place][eve][od][temp]의 값을 채워 나갑니다.
현재 요소의 초기값으로 count = 0을 설정합니다.
현재 위치가 마지막 자리인지 if(place == vec.size())로 확인하고, 맞다면 해당 위치가 홀수인지 짝수인지 판단합니다.
if(vec.size() & 1)이 참이면 자릿수 길이가 홀수이므로 eve와 od를 서로 교환(swap)합니다.
두 합의 차이 temp_2 = eve − od를 계산합니다.
for 반복문으로 arr_2[]를 순회하며 temp_2가 존재하는지 확인합니다. 존재하면 소수이므로 1을 반환하고, 아니면 0을 반환합니다.
arr[place][eve][od][temp]가 이미 계산된 값이라면 -1이 아니므로 해당 값을 그대로 반환합니다(메모이제이션).
temp가 0이 아니라면 temp_3 = 9로 설정합니다. temp_3은 현재 자리에 놓을 수 있는 최대 자릿수입니다. temp가 0이면 아직 상한선에 도달하지 않은 것이므로 vec[place] 값을 사용하고, 이미 작아진 상태라면 어떤 자릿수든 놓을 수 있으므로 9를 사용합니다.
0부터 temp_3까지 자릿수를 순회하며, 현재 위치가 홀수 자리면 set_odd에 i를 더하고, 짝수 자리면 set_even에 i를 더합니다.
count += check(place + 1, set_even, set_odd, set_temp, vec);로 누적한 뒤 arr[place][eve][od][temp] = count를 반환합니다.
함수 place_prime(int val)은 숫자 val을 받아 자릿수를 최상위 자리(MSB)부터 최하위 자리(LSB) 순서로 벡터 vec에 담습니다.
배열 arr[][][][] 전체를 -1로 초기화합니다.
check(0, 0, 0, 0, vec)를 호출하여 최종 결과를 반환받습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
const int size = 18;
int arr[size][90][90][2];
// 100 이하의 소수들
int arr_2[] = {
   2, 3, 5, 7, 11,
   13, 17, 19, 23, 29,
   31, 37, 43, 47, 53,
   59, 61, 67, 71, 73,
   79, 83, 89, 97
};

int check(int place, int eve, int od, int temp, vector < int > vec) {
   int count;
   int temp_3;
   if (place == vec.size()) {
      if (vec.size() & 1) {
         swap(od, eve);
      }
      int temp_2 = eve - od;
      for (int i = 0; i < 24; i++) {
         if (temp_2 == arr_2[i]) {
            return 1;
         }
      }
      return 0;
   }
   if (arr[place][eve][od][temp] != -1) {
      int set = arr[place][eve][od][temp];
      return set;
   }
   if (temp) {
      temp_3 = 9;
   } else {
      temp_3 = vec[place];
   }
   for (int i = 0; i <= temp_3; i++) {
      int set_temp = temp;
      int set_even = eve;
      int set_odd = od;
      if (i < vec[place]) {
         set_temp = 1;
      }
      if (place & 1) {
         set_odd = set_odd + i;
      } else {
         set_even = set_even + i;
      }
      count += check(place + 1, set_even, set_odd, set_temp, vec);
   }
   return arr[place][eve][od][temp] = count;
}

int place_prime(int val) {
   vector < int > vec;

   while (val) {
      vec.push_back(val % 10);
      val = val / 10;
   }
   reverse(vec.begin(), vec.end());
   memset(arr, -1, sizeof(arr));
   int count = check(0, 0, 0, 0, vec);
   return count;
}
int main() {
   int start = 20, end = 80;
   int count = place_prime(end) - place_prime(start - 1);
   cout << "짝수·홀수 위치 자릿수 합의 차이가 소수인 범위 내 숫자의 개수: " << count;
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

짝수·홀수 위치 자릿수 합의 차이가 소수인 범위 내 숫자의 개수: 15

이처럼 동적 계획법과 메모이제이션을 활용하면 범위 내 모든 숫자를 일일이 검사하는 것보다 훨씬 효율적으로 조건을 만족하는 숫자의 개수를 구할 수 있습니다.