어흥

문제 링크: www.acmicpc.net/problem/15809 15809번: 전국시대 첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000) 다 www.acmicpc.net 1. 주의할 점 - 동맹 처리를 어떻게 할 것인가? - 전쟁 처리를 어떻게 할 것인가? 빠트린 조건은 없는가 2. 구현 - 동맹 처리: 공통조상 설정 + 공통조상으로 병력합친다 - 전쟁 처리: 병력 감소 + 한 국가 멸망 + 속국 처리(이 부분을 까먹기 쉽다) - Par[] 배열을 통해 자신의 조상을 나타낸다 - Power[] 배열을 통해 한 나라..

문제링크: www.hackerrank.com/challenges/kruskalmstrsub/problem Kruskal (MST): Really Special Subtree | HackerRank Learn to use the Kruskal's algorithm ! www.hackerrank.com 1. 주의할 점 - 간선의 가중치가 같다면 각 Node의 합이 작은것을 우선시한다 - Make_union() 함수에서 부모를 잘 갱신하도록 한다 2. 구현 - 입력받는 모든 간선에 대한 정보를 우선순위큐 PQ에 넣는다 - PQ에서 꺼낸 간선에서 양 끝점이 만약 같은 집합이 아니라면 Make_union()함수를 통해 이어주며 Result에는 가중치만큼 더하며 Cnt++를 통해 MST의 경우 Node의 개수-1만..

문제 링크: www.hackerrank.com/challenges/torque-and-development/problem Roads and Libraries | HackerRank Help the ruler of HackerLand determine the cheapest way to give his citizens access to libraries. www.hackerrank.com 1. 주의할 점 - 범위를 잘 확인한다 - 각 쿼리마다 초기화를 잘 수행한다 - 입력받은 길 중에서, 도서관을 1개 세우는 경우: (Cnt-1)*C_road + C_lib만큼의 비용이 발생하고 각각 도서관을 세우는 경우: Cnt*C_lib만큼의 비용이 발생한다. 즉 C_road>=C_lib일때, 각각 도서관을 세우면 된다..

문제 링크: https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 1. 주의할 점 - 분리집합으로 집단을 나눈 이후, 그 집단에서 가장 작은 친구비를 더한다 2. 구현 - 입력을 받으면서 Par[](자신의 조상을 나타냄)배열을 초기화한다 - 친구 관계를 입력받을 때, 같은 집합이 형성되도록 Make_union() 함수를 사용한다. 그리고 Make_union() 함수를 사용할 때, 작은 친구비를 가진 학생..