boj, 백준) 1733.등번호 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1733 1733번: 등번호 첫째 줄에 티셔츠의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 이후 N개의 행에 각 티셔츠의 정보가 두 개의 자연수로 주어진다. 이는 티셔츠의 안쪽과 바깥쪽에 적힌 등번호이다. 각 등번호는 1이상 www.acmicpc.net 2. 문제 개요 한 선수가 최대 두 가지의 번호를 부여받을 수 있다. 각 선수들이 어떤 번호를 선택해야 모든 선수들의 번호가 중복되지 않을 수 있을지 구하는 문제. 3. 문제 힌트 일반적인 O(VE)시간복잡도의 이분 매칭으로는 시간 초과다. 호프 크로프트 카프 알고리즘 O(V^(1/2) E)을 사용하자. 그리고 불가능하다면 불가능한 선수만 -1로 출력하지말고 전체 출력..
boj, 백준) 1017. 소수 쌍 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23 또는 1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23 수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 www.acmicpc.net 2. 문제 개요 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 남는 수 없이 모두 쌍을 ..
boj, 백준) 2191. 들쥐의 탈출 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/2191 2191번: 들쥐의 탈출 첫째 줄에 네 정수 N, M, S, V가 주어진다. 다음 N개의 줄에는 들쥐의 x, y좌표가 주어지고, 그 다음 M개의 줄에는 땅굴의 x, y좌표가 주어진다. 모든 좌표는 절댓값이 1,000을 넘지 않는다. www.acmicpc.net 2. 문제 개요 매에게 잡아먹히지 않기 위해 들쥐들은 땅굴로 도망가야 한다. 하지만 땅굴로 도망치는 속도가 있기 때문에 항상 모든 쥐들이 도망갈 수 있는 것은 아니다. 들쥐와 땅굴의 위치, 그리고 들쥐의 속도와 매가 도착하는 시간이 주어졌을 때, 잡아먹히게 되는 들쥐들의 최소수를 구하는 프로그램을 작성하자. 3. 문제 힌트 들쥐와 땅굴을 이분그래프로 만든다. 4. 문..
boj, 백준) 11377. 열혈강호 3 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. www.acmicpc.net 2. 문제 개요 직원 N명, M개의 일 N명 중에서 K명은 일을 최대 2개 할 수 있을 때, 일을 최대 몇 개를 할 수 있는지 구하는 프로그램 작성하기. 3. 문제 힌트 K명은 일을 한번 더 할 수 있다는 말은 일 1개씩 하는 이분매칭 + 최대 K = 답이 된다. 즉, 이분탐색을 한번 더 하고 누가 됐든 간에 어느..
boj,백준) 11376. 열혈강호2 (C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 개요 직원이 N명 있고 1~N번으로 번호가 매겨져 있다. 일은 1번부터 M번까지 번호가 매겨져 있다. 이때, 각 직원은 최대 두 개의 일을 할 수 있고, 각각의 일을 담당하는 사람은 1..
boj, 백준) 11375. 열혈강호 (C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 개요 직원이 N명 있고 할 일이 M개가 있다. 각 직원이 할 수 있는 일의 번호가 주어졌을 때 최대 몇 개를 할 수 있는지 구하는 프로그램 작성. 3. 문제 힌트 이분매칭 알고리즘을 알아야 한다..