[백준 / BOJ] 1202 보석 도둑 - (유니온 파인드, 이분탐색)
문제 출처 : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 상덕이는 보석을 털기로 결심했다. 보석점에 총 N개의 보석이 있고, 각 보석은 M의 무게, V의 가격을 갖고있다. 상덕이는 K개의 가방을 갖고있고, 각 가방에는 최대 Ci무게의 보석을 담을수있다. 이때, 각 가방에는 최대 한개의 보석만 담을수있다. 상덕이가 홈칠수있는 보석의 최대 가격을 출력하는 문제다. 풀이 보석의 수 N..
[백준 / BOJ] 14595 동방 프로젝트 (Large)
문제 출처 : www.acmicpc.net/problem/14595 14595번: 동방 프로젝트 (Large) 첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다. www.acmicpc.net 동아리방을 합치는 연산이 여러번 주어졌을때, 이 연산이 모두 끝난후, 남아있는 방의 수를 출력하는 문제다. 풀이 시간초과를 피하기위해 유니온파인드를 이용해서 풀어야한다. 방이 총 5개있을때, 각 방은 이런식으로 떨어져있을것이다. (예제 1) 이때, 1번방과 2번방을 합치는 연산을하면 1번방과 2번방은 같은방이되는데, 그걸 이렇게 연결..
