30469 c++ - 호반우가 학교에 지각한 이유 2

소수찾기 문제의 심화버전이다. 알고리즘 분류는 애드 혹이다.

체를 사용하여 최적해를 구할 수 있도록 하였다.

 

 

c++ 코드

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
bool prime[100];

void savePrime() {
  memset(prime, true, sizeof(prime));
  prime[0] = prime[1] = false;
  for (int i = 2; i < 100; ++i) {
    if (prime[i]) {
      for (int j = i * i; j < 100; j += i) {
        prime[j] = false;
      }
    }
  }
}

bool checkPrime(int a, int b) {
  int c = a * 10 + b;
  return c >= 10 && c < 100 && prime[c];
}

bool findPrimeSequence(int a, int b, int n, vector<int>& number) {
  number[0] = a / 10;
  number[1] = a % 10;

  for (int i = 2; i < n - 2; ++i) {
    bool found = false;
    for (int d = 1; d <= 9; ++d) {
      if (checkPrime(number[i - 1], d)) {
        number[i] = d;
        found = true;
        break;
      }
    }
    if (!found) return false;
  }

  number[n - 2] = b / 10;
  number[n - 1] = b % 10;

  return checkPrime(number[n - 3], number[n - 2]) &&
         checkPrime(number[n - 2], number[n - 1]);
}

int main() {
  savePrime();

  int a, b, n;
  cin >> a >> b >> n;

  if (!prime[a] || !prime[b]) {
    cout << "-1";
    return 0;
  }

  vector<int> number(n, 0);
  if (findPrimeSequence(a, b, n, number)) {
    for (int digit : number) cout << digit;
  } else {
    cout << "-1";
  }
  return 0;
}