글 읽기 - [1017번] 재귀함수 / 소수계산

iwyoo 9년 전 0

1017번 문제입니다. 시간초과로 풀리지 않고 있습니다.

재귀함수를 사용하여 모든 경우를 다 탐색하는데,

함수콜에 시간이 오래 걸리는 건지, 소수인지를 파악하는데 시간이 오래걸리는 건지 잘 모르겠습니다.

어떤 점이 문제일까요?

#include <stdio.h>

int pairing(int l, int r, int n);

int list[50];
int used[50];
int isPrime[50*50];
int first;
int n;

int main()
{
    int i,j,k,p;
    first = 1;

    scanf("%d",&n);

    i=0;
    while (i<n) {
        scanf("%d",&list[i]);
        used[i] = 0;
        i++;
    }

    // 모든 두 쌍의 합에 대해 소수인지 판별하는 과정
    for (i=0; i<n; i++)
        for (j=i+1; j<n; j++) {
            k=2;
            for ( ; k*k < list[i]+list[j]; k++) {
                if ((list[i]+list[j])%k==0) {
                    p = 0; break;
                }
                p = 1;
            }
            isPrime[i*50+j] = p;
        }

    // 가능한 경우를 판단하고 출력하는 과정
    for (i=1; i<n; i++) {
        if (isPrime[i] && pairing(0,i,n-2)) {
            if (first) {
                printf("%d",list[i]);
                first = 0;
            } else {
                printf(" %d",list[i]);
            }
        }
    }

    if (first)
        printf("-1");
    printf("\n");

    return 0;
}

// 쌍을 묶는 재귀함수
int pairing(int l, int r, int k)
{
    if (k == 0) return 1;

    used[l] = 1;
    used[r] = 1;

    int x,y,ret=0;
    for (x=l+1; x<n-1; x++)
        if (!used[x]) break;

    for (y=x+1; y<n; y++) {
        if (!used[y] && isPrime[x*50+y])
            ret |= pairing(x,y,k-2);
    }

    used[l] = 0;
    used[r] = 0;

    return ret;
}

portableangel 9년 전 0

재귀호출로 해결하기에는 입력의 양이 너무 많습니다. 예를 들어 50개의 수가 서로 묶어서 항상 소수가 될 수 있다면

가능한 모든 경우를 탐색하는 데에 50C2 * 48C2 * ... * 2C2 , 약 50!/(2^25)회 정도의 재귀호출을 하게 됩니다.

(아마도) 정해는 이분 매칭입니다. 입력으로 주어지는 수가 모두 서로 다르기 때문에 항상 홀수+홀수와 짝수+짝수는 소수가 될 수 없으므로

홀수 그룹과 짝수 그룹으로 나누어 첫 수를 우선 매칭시키고 그 이후 최대 매칭이 n/2-1개가 되는지 확인하는 코드로 O(n^4) 미만의 시간에 해결할 수 있습니다.

iwyoo 9년 전 0

설명 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[1017번] 재귀함수 / 소수계산

iwyoo 9년 전 0

portableangel 9년 전 0

iwyoo 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말