백준 1017번 소수 쌍

문제 링크입니다: https://www.acmicpc.net/problem/1017

 

소수 관련된 문제이므로 에라토스테네스의 체와 이분 매칭을 통해 풀 수 있는 문제였습니다.

저도 처음에 백트래킹으로 접근했다가 TLE가 발생했던 문제입니다 ㅠ

 

알고리즘은 다음과 같습니다.

1. nums[0]과 합쳤을 때 소수를 이루는 nums[i]를 매칭합니다.

2. 남은 수들로 이분 그래프를 만드는데 왼쪽 집합은 홀수인 수들, 오른쪽 집합은 짝수인 수들로 구성하며 간선은 두 수의 합이 소수일 때 연결시킵니다.

3. 이분 그래프에서 최대 매칭을 찾아서 모든 노드가 매칭에 포함되는지 확인합니다.

3.1 매칭의 크기가 남은 노드의 절반이라면 모든 수를 짝지을 수 있다는 의미입니다.

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~