leechhe   11달 전

방문 여부는 비트마스킹으로 하였고, 재귀 호출로 모든 경우의 수를 탐색했습니다.

나름 케이스를 넣어 봤었는데 ㅠㅠ 모르겠네요.

그리고 혹시 이렇게 푸는 건 맞는 건가요? 고쳐도 시간 초과 뜰 거 같은데...

1. 입력이 오름차순이라는 조건이 없습니다. 마지막에 ans 배열을 한 번 소팅해줘야 합니다.

2. 사실 이분 매칭으로 간단히 풀 수 있습니다. 주어지는 수들이 서로 다르기 때문에 두 수의 합은 3 이상이 되고,

따라서 어떤 두 수의 합이 소수이기 위해서는 홀수여야만 하므로 각 입력된 수들을 노드로 하고

합이 소수가 되는 쌍 사이에 간선을 이으면 짝수와 짝수, 홀수와 홀수 사이엔 간선이 없고

일부 짝수와 홀수 쌍 사이에만 간선이 있게끔 모델링되며 이에 따라 짝수 그룹과 홀수 그룹으로 이루어진 이분 그래프가 됩니다.

첫 노드를 미리 다른 하나와 매칭시키고, 나머지 그룹에서 최대 매칭이 되는지의 여부를 n-1번 체크하면 됩니다.

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