[4241] 소수 없는 수열

난이도: Gold III ± 0.0 (σ = 0.0)

체감 난이도: Gold II - 0.2

 

태그

• Backtracking (백트래킹)
• Sieve of Eratosthenes (에라토스테네스의 체)
• Unknown Time Complexity (시간복잡도가 :blobthinking:)

 

풀이

1. 나올 수 있는 합의 최댓값은? 이를 토대로, 소수 판정을 해보자면?

(수열의 길이) × (연속된 합의 길이), 즉 \( (M-N) \times D \)가 됩니다.

문제 제한 상으로는, 약 10000이 되겠네요.

 

이걸 알고 있으니, 10000까지의 수에 대해 에라토스테네스의 체를 돌려두면

소수 판정의 시간복잡도는 더 이상 신경쓰지 않아도 됩니다.

 

2. 이걸로, 가능한 경우를 돌려보자면?

백트래킹을 사용하여 하나씩 돌려본다고 해봅시다.

\( f(A) \)에서는 prefix가 \( A \)인 수열만 본다고 하면, 이 함수의 결과는 아래 둘 중 하나가 됩니다.

• \( A \)가 \( n \)부터 \( m \)까지의 모든 수를 다 가지고 있을 경우: 이미 답을 찾았으니, 출력 후 종료하면 됩니다.
• 아닌 경우: \( x \notin A \)인 \( x \)에 대해, 만약 \( x \)를 넣어도 \( d \)차 수열의 조건을 위해하지 않는다면, \( f(A + [x]) \)를 호출해보면 됩니다.

 

3. 조건 판정은 어떻게 빠르게 할까? (from [2번])

백트래킹 함수의 특성상, 수열 \( A \)는 이미 조건을 잘 만족하고 있습니다.

그러니, \( A \)의 맨 뒤에 \( x \)를 추가로 넣는다면, \( x \)가 포함되는, suffix만 고려하면 됩니다.

 

어차피 \( 2 \)개의 합부터 \( d \)개의 합까지 다 봐야 하므로, \( A \)의 뒷부분에서부터 1개씩 더하면서 판정해주면 됩니다.

 

4. 시간복잡도... 괜찮은가?

사실 모르겠습니다. 가지치기가 동반된 백트래킹 문제 특성이긴 하지만요.

 

코드

const int N = 10000;
int n, m, d, len;
bool pr[10020];
 
int arr[1020]; bool chk[1020];
bool btk(int idx){
    //cout << "BTK " << idx << endl;
    if (idx > len){
        for (int i = 1; i <= len; i++){ cout << arr[i] << ",\n"[i==len]; }
        return 1;
    }
    for (int x = n; x <= m; x++){
        if (chk[x]){ continue; }
        int ed = max(idx-d, 0); int sum = x;
        bool flg = 1;
        for (int j = idx-1; j > ed; j--){
            sum += arr[j]; if (pr[sum]){ flg = 0; }
        }
        if (flg){
            chk[x] = 1; arr[idx] = x;
            if (btk(idx+1)){ return 1; }
            chk[x] = 0; arr[idx] = 0;
        }
    }
    return 0;
}
 
void Main(){
    memset(pr, 1, sizeof(pr)); pr[0] = pr[1] = 0;
    for (int p = 2; p <= N; p++){
        if (!pr[p]){ continue; }
        for (int x = p+p; x <= N; x+=p){ pr[x] = 0; }
    }
    while (1){
        cin >> n >> m >> d; len = m-n+1;
        if (n==0 && m==0 && d==0){ return; }
        memset(chk, 0, sizeof(chk)); memset(arr, 0, sizeof(arr));
        if (!btk(1)){ cout << "No anti-prime sequence exists." << endl; }
    }
}