백준 1017번 - 소수 쌍
https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 필요한 배경지식 이분매칭 소수판정 - (에라토스테네스의 체) 문제 해결 방법 이분매칭을 이용하면 됩니다. 우선 두 수를 더한 값이 소수일때 두 수를 연결하는 간선을 추가하여 그래프를 만들어야 합니다. 그 다음 이분매칭을 하여 매칭된 쌍의 개수가 N/2개일때 첫 번째 수와 짝지어진 수를 출력하면 됩니다. 소수를 판정할 때에는 두 수를 더한 값이 최대 ..
알고리즘 공부/문제풀이
2021. 6. 9. 21:24
반응형