본문 바로가기

이분매칭6

백준 16726 / C++ https://www.acmicpc.net/problem/16726 16726번: 영과일 학회방 영과일은 학회방이 없어질 위기에 처했지만 우수한 학회원들의 실력을 인정받아 학회방을 다시 배정 받을 수 있었다! 이에 행복해진 영과일 총무부장 재현이는 새로운 마음으로 1 × 2, 1 × 1 타 www.acmicpc.net [ 풀이 ] 예제 생긴것부터 플로우 문제네요. n제한도 작으니... 격자판을 1*2 와 1*1로 채울 수 있습니다. 최소개수가 필요하니 1*2들을 최대한 써줘야 합니다. 격자를 체스판처럼 컬러링한 후 색이 다른걸 이분매칭을 돌려주면 됩니다. 이분매칭으로 최대한 찾은 결과가 k라고 하면, 'X'를 제외한 면적에서 2k가 빠집니다. 그럼 나머지 S-2k는 1*1로 채워야 하므로 S-2k개가 필.. 2022. 8. 31.
백준 1017 / C++ https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net [ 풀이 ] 홀짝성을 기준으로 이분그래프로 모델링하자. a[0]가 있는쪽을 왼쪽집합으로 두자. 전부 소수가 되게 매칭을 하려면 우선 왼쪽,오른쪽 집합 크기가 같아야 하고, 최대매칭의 크기가 집합 크기와 같아야 한다. 이제 a[0]와 매칭되는 걸 출력까지 해야되기 때문에 a[0]와 매칭될 수를 먼저 선택한다. 이제 나머지 그래프에서 최대매칭이 크기-.. 2022. 8. 17.
백준 9525 / C++ https://www.acmicpc.net/problem/9525 9525번: 룩 배치하기 체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이 www.acmicpc.net [ 풀이 ] X를 기준으로 열과 행들이 나뉜다. 나뉜 열과 행들에 각각 순번을 매겨주자. 한 칸에 룩을 놓는 행위는 그 칸의 행과 열을 매칭시켜준다고 볼 수 있다. 또한 룩은 서로 공격할 수 없으므로 한 행에 대해 한 열을 택했다면, 다른 행은 이 열을 택할 수 없으므로 결국 이분매칭에서 최대매칭수를 찾아주면 된다. 구현이 좀 복잡한데 map으로 각 칸 (i,j)에 대해 연결여.. 2022. 8. 17.
백준 2191 / C++ https://www.acmicpc.net/problem/2191 2191번: 들쥐의 탈출 첫째 줄에 네 정수 N, M, S, V가 주어진다. 다음 N개의 줄에는 들쥐의 x, y좌표가 주어지고, 그 다음 M개의 줄에는 땅굴의 x, y좌표가 주어진다. 모든 좌표는 절댓값이 1,000을 넘지 않는 실수이며 소숫 www.acmicpc.net [ 풀이 ] 거리가 SV 이하면 연결해주고 최대매칭을 구해주면 됩니다. 답은 N-최대매칭 이 되겠네요. [ Code ] #include using namespace std; struct pdd { double x, y; }; vectorg[111]; double s, v; int n, m, par[111], vis[111]; pdd a[101], h[101]; double.. 2022. 8. 17.

티스토리툴바