iwyoo   1년 전

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

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

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

어떤 점이 문제일까요?

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

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

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

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

iwyoo   1년 전

설명 감사합니다!

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