반응형
1017번
-
1017번 : 소수 쌍알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 31. 16:11
https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 집합에 속한 임의의 원소 두개의 합이 소수가 되도록 모두 짝지었을 때 첫 번째 원소와 짝지은 원소들을 오름차순으로 출력하는 문제다. 아이디어, 구현 : 네트워크 플로우(이분매칭)으로 해결할 수 있었다. 하지만 조금 특이한 방식으로 해결했다. 먼저, 모든 수를 두개로 늘려서 짝지을 첫번째 원소, 짝지을 두번째 원소로 나누었다. 첫 번째 원소는 제외하..