1. 문제 1202번: 보석 도둑 (acmicpc.net) 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 2. 풀이 이 문제는 탐욕법으로 해결할 수 있다. 가장 값비싼 보석을 가능한 가방중 가장 용량이 작은것에 넣는 것이다. 하지만 배열을 사용하여 문제를 풀 시 시간초과가 나온다. 따라서 적절히 사용한 가방을 제외 하고, 빠르게 작은 가방을 찾을 수 있는 자료구조를 사용해야한다. map을 사용하면 빠르게 원소를 제외할 수 있고, 최소 원소 또한 찾..

1. 문제 반 학생들의 체육복이 도난당했다. 도난당한 학생의 번호와 여유분을 가진 학생의 번호가 주어진다. 여유분을 가진 학생이 도난당한 학생에게 체육복을 빌려줄때 체육복을 최대한 나눠주고, 체육수업을 들을 수 있는 최대 학생수를 구하여라 단, 체육복은 자신의 앞뒤 번호한테만 빌려줄 수 있다. 단, 여유분을 가지고 있던 학생이 도난당했을 수 있다. 그러면 빌려주지 않는다. 2. 자원분배 문제: 네트워크 플로 이 문제는 이분 그래프의 최대매칭 문제로 네트워크 플로로 풀 수 있다. 여유분 그룹에서 도난 그룹으로가는 그래프를 그린 후 네트워크 플로우 알고리즘을 사용하면 문제가 해결된다. 단, 여유분을 가지고 있던 학생이 도난당할경우 그래프를 그리지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13..

1. 크리스마스 인형 이 문제는 두가지의 문제를 풀어야한다. 선물상자의 인덱스 0~n 주문한번: a번 박스 부터 b번 박스까지 구매 1. 산타가 아이들에게 같은양의 선물을 주고 남은 나머지가 0인 상자의 구간의 개수 2. 산타가 아이들에게 띄엄 띄엄 주문해서(중복x) 주문한번당 아이들에게 나머지 없이 나누어주는 최대의 주문 수 2. 1번 문제 1번문제에서 이 문제는 부분 구간의 부분합을 구해야한다는 것을 알 수 있다. psum[a] = 0~a 까지의 합 order(a, b) = a 에서 b까지 주문하고 총 인형의 개수 라고 하자. 아이들한테 남는거 없이 선물하므로, order(a, b) % child == 0 이 되어야함을 알 수 있다. order(a, b) = psum[b] - psum[a-1] ord..

1. 문제의 데이터를 변형해야한다. 초소의 실수 좌표들이 주어지고, 반지름이 주어진다. 이 데이터들을 가공하여 문제를 바로 푸는 것은 까다롭다. 그러므로 책에서는 이 데이터들을 중심각 구간으로 표현하였다. 중심각 이외에 원과 원이 만나는 X축 구간으로도 풀 수 있을것 같다. 2. 탐욕법 각 초소들의 구간으로 나타내면 이것은 활동 선택문제와 매우 유사하다. 하지만 이 문제는 처음 구간을 고르는게 중요하다. 원은 순환하기 때문에 처음 구간은 맨 마지막 구간과 이어지기 때문이다. 전체 구간이 0~2π 라고 할때 0 을 포함하는 구간들은 항상 두개 이하 선택 해야한다. 맨 오른쪽, 맨 왼쪽에 해당하는 구간 두개가 있으면 항상 다른 구간들은 그 구간에 포함되기 때문이다. 그리고 0 을 포함하는 구간들을 지금 선택..

1. 탐욕법 문자들을 합쳐 문자열을 만드는데 드는 비용이 최소가 되게 선택하려면 일단 가장 작은 문자 두개를 선택해 합쳐나가야 할 것 같다. 합쳐진 문자열에 또 합치게 되면 이전에 합치게한 문자열이 중복으로 또 다시 카운트 되기 때문이다. 2. 증명 탐욕적 선택 속성을 증명하기 위해 먼저 가장 작은 두 문자가 서로 합쳐지지 않은 최적해가 있다고 해보자 a와 b가 가장 작은 두 수 일때 먼저 다른 문자열과 합친것을 다음과 같이 표현했다. X = b + B Y = a + C 거리가 같은경우 : X + Y 일 경우 a 와 B를 바꾸어도 비용은 일정하므로 답은 변하지 않는다 거리가 다른 경우: X + a 일경우 a와 B를 바꾸게 될경우 B가 병합되는 횟수가 적어져 비용이 줄어들게 된다. 그러므로 작은 두 문자열..

1. 탐욕법 이 문제는 전자레인지를 데우는 시간의 총 합은 변하지 않는다 이 총합과 어떤 음식하나를 다 먹는 시간 의 합의 최소값이 문제에서 구하라는 해이다. 점심시간을 최소화하기 위해서 일단 음식하나에의해 좌우 되니 음식 먹는 속도가 느린 사람이 제일 먼저 전자레인지를 돌릴꺼 같다. 2. 증명 만약 음식 먹는 속도가 느린사람이 첫번째로 안오는 최적해를 생각해보자 맨 처음 사람과 속도가 제일 느린 사람의 순서를 바꿔보자 순서를 바꿔도 최적해인것에는 변함이 없다. 그러므로 속도가 느린 사람부터 선택하는 방법은 최적해에 포함된다. 부분문제 또한 자명하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32..