11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 3일 전에 틀리고 '블로그에 옮기면서 다시 한번 봐야지' 했는데 이제야 쓴다. 분명 이분 매칭 문제를 푼 기억이 있는데, 문제를 보고 이분 매칭을 떠올리지 못했다. 이분 매칭을 잘 설명한 글 [알고리즘] 이분 매칭 알고리즘 (Bipartite Matching) 이분 매칭 알고리즘 (Bipartite Matching) 두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프(Bipartit..
전체 글
16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 문제를 이해하는 데 시간이 좀 걸렸었다. 구현해야 할 내용을 정리하자면 아래와 같다. 1. 매 턴마다 MST를 만든다. 2. MST가 완성됐다면 MST의 비용을 출력하고, 해당 MST에서 가장 비용이 작은 간선을 제거한다. 3. MST가 완성되지 않았다면 해당 턴부터 마지막 턴까지 0을 출력한다. 문제에서 주어진 대로 계산했을 때 간선 개수는 최대 50만 개다. 그렇기 때문에 제거할 간선에 대한 표시..
16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 단순 그리디라고 생각해서 작은 것부터 자를 수 있는 만큼 잘라나가는 식으로 했지만 실패했다. 왜 틀렸을까 생각해 보니 1. 길이가 20인 롤케이크는 한 번 잘라서 길이 10인 롤케이크를 2개 만들 수 있다는 점 2. 길이가 10의 배수인 롤케이크를 길이가 10으로 나누어 떨어지지 않는 롤케이크 보다 먼저 자르는 게 이득일 것이라는 점 이 같은 점들을 고려해서 1. 10으로 나누어 떨어지는 것들을 오름차순으로 앞에 오도록, 2. 10으로 나누어 떨어지지..