0과 1의 쉼터

풀이 n개의 티셔츠와 m개의 세일러 카라에 대한 bipertite matching 문제이다. 단, 모든 티셔츠가 모든 세일러 카라에 대한 매칭이 가능한 것이 아니다. 문제에서 주어진 아래의 조건을 만족하는 경우에만 매칭이 가능하다. 하얀 티셔츠의 너비를 정수 w라고 할 때, 여기에 붙일 수 있는 세일러 카라는 두 가지가 있다. 너비가 w/2 이상 w×3/4이하인 세일러 카라를 붙일 수 있다. 카라가 옷보다 살짝 더 넓게 만들어서 너비가 w 이상 w×5/4 이하인 카라를 붙일 수 있다 티셔츠에 대해 입력받은 세일러 카라의 너비를 위의 조건에 맞게 미리 만들어준다면, 티셔츠별로 살펴봐야 하는 불필요한 카라들이 너무 많아진다. 때문에 일단은 너비만 입력받고, 매칭하는 과정에서 위의 너비에 대한 조건을 만족해 ..

풀이 학생 N명에 대해 고를 수 있는 노트북 최대 N개에 대한 bipartite matching 기본 문제다. 노트북의 번호에 관계없이 최대 N개만 존재하기 때문에 배열을 N에 맞춰 match, visited 배열의 크기를 지정해주자. 소스코드 소스코드 보기 출처 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net

풀이 두 그룹이 있을 때, 모든 간선이 가중치가 1이고 다른 그룹으로만 향하는 그래프를 Bipartite Graph 라고 한다. 이 때, 간선을 통해 다른 정점을 점유한 상태를 matching한다고 하며 Bipartite Graph에 대한 matching을 Bipartite Matching이라고 한다. 즉, 간선의 가중치가 전부 1인 Bipartitle Graph에서 maximun flow을 구해주는 문제는 maximun matching을 구해주는 문제와 동일하다. 때문에 간단하게 DFS를 이용해 O(VE), O((N+M)E) 안에 구현하는 방법을 사용할 수 있다. 최종적으로 연결된 정점을 기록할 match 배열과, 바로 매칭이 되지 않은 경우(다른 정점과 이미 매칭된 경우) 현재 정점을 최종적으로 매칭..

풀이 M명에 대해 N권의 책을 최대한 많은 학생에게 주는 문제다. greedy와 bipartite matching 둘다 풀이해보았다. Greddy 최대한 많은 인원에게 주기 위해서는 최대한 균등하게 나누어서 주어야 한다는 사실은 자명하다. 어떤 기준으로 나누어 줄까? 다음의 경우에 대해 생각해보자. (a, b)가 { (1, 4), (1, 5), (1, 2) } 일 때의 경우다. 3명 다 a = 1 동일한 상태이고, b만 다른 경우다. 위에서 순서대로 2, 3, 1번 책을 가져가면 3명 모두 다 책을 가지고 갈 수 있고 (1, 5) 구간에 대해서는 다르게 책을 가지고 가는 방법이 존재할 수 있다. 그 중 중요히 여겨야 할 부분은 바로 a가 동일한 3명에 대해서도 구간(b)이 작은 순서대로 가져가는 방법이 ..