문제 링크 http://icpc.me/2679 2679번: 맨체스터의 도로 맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 www.acmicpc.net 풀이 네트워크 플로우를 기반으로 하고, 우선순위 큐를 이용한 풀이와 이분 탐색을 이용한 풀이가 있다. 차의 개수는 네트워크 플로우를 이용하면 쉽게 구할 수 있지만, 길 1개를 이용할 때의 최대 개수는 구하기 어렵다. 일반적인 네트워크 플로우처럼 경로를 고른다면, 경로를 고르는 순서에 따라 어떤 길에 한 번에 보낼 수 있는 최대를 보내지 않을 수 있다. 그렇기 때문에 다른 처리를 해줘야 한다. 우선순위 큐 풀이 ..

문제 링크 http://icpc.me/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 모든 조합을 뽑아서 확인해보면 O(2^40)이기 때문에 시간이 터진다. 그렇기 때문에 반절로 나눠서 모든 조합을 확인해봐야 한다. x + y = s를 이용하여 오른쪽 조합에서 하나를 뽑아 s - y가 왼쪽 조합에 몇 개 존재하는지 이분 탐색을 이용하여 확인하면 모든 경우를 확인할 수 있다. 이때 몇 개가 존재하는지 확인할 때 upper_bound - lower_bound를..

문제 링크 http://icpc.me/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 풀이 결정문제로 바꿔 이분 탐색을 하여 풀 수 있다. m명에게 길이가 n인 과자를 줄 수 있는지 없는지 판단하는 문제로 바꿔, 길이 n을 이분탐색을 돌리면 된다. 이렇게 풀면 O(NlogN)에 풀 수 있다. 코드 #include int arr[1000006]; int main() { int m, n; scanf("%d %d", &m, &n)..