https://www.acmicpc.net/problem/15554 15554번: 전시회 승원이는 미술품 N개를 가지고 있다. 각각의 미술품은 1번부터 N번까지 번호가 매겨져 있다. i번 미술품의 크기는 Ai, 가치는 Bi로 나타낸다. 오늘은 승원이의 저택 1층에서 미술품을 전시하려고 www.acmicpc.net 미술품의 크기와 가치를 저장해서 (크기, 가치)로 정렬한 뒤, 가치의 누적합을 계산한다. B~A(B n; for (int i = 1; i > a >> b; info[i] = make_pair(a, b); } sort(info.begin() + 1, info.begin() + n + 1); //정렬 //가치 누적합 계산 for (int i = 1; i

https://www.acmicpc.net/problem/21279 > n >> c; for (int i = 0; i > x >> y >> v; gold_x[x].push_back(make_pair(y, v)); gold_y[y].push_back(make_pair(x, v)); } //x지점은 큰쪽에서 작은쪽으로 범위를 줄이고, y지점은 작은 쪽에서 큰쪽으로 범위를 늘리는 투포인터로 범위 탐색 int check_x = 100000; //check_x는 오른쪽 끝에서 왼쪽으로 움직이고(범위를 줄이는 방향) int check_y = 0; //check_y는 아래에서 위쪽으로 움직인다(범위를 늘리는 방향) long long check_value = 0; ..

https://www.acmicpc.net/problem/2197 2197번: 분해 반응 첫째 줄에 두 정수 N, M(1 ≤ M ≤ N)이 주어진다. 다음 N-1개의 줄에는 원자들의 연결 상태를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 원자와 B번 원자가 결합을 이루고 www.acmicpc.net 루트가 1번 노드인 트리를 만들고, 리프 노드부터 위로 올라가면서 cache[노드][크기]에 해당 노드가 루트인 서브 트리에서 해당 크기로 만드는데 최소로 자르는 횟수를 채운 뒤, 모든 노드를 확인하며 각 노드에서 크기 m을 만드는데 자르는 최소 횟수 중 가장 작은 값을 찾는 방법으로 문제를 해결했다. 각 노드의 cache를 채울 때 해당 노드의 자식 노드를 이용했는..

https://www.acmicpc.net/problem/5021 5021번: 왕위 계승 유토피아의 왕이 사망했다. 왕은 자손을 남기지 않고 사망했기 때문에, 왕위를 계승할 사람을 지목하지 않았다. 왕실 귀족은 왕위를 주장하기 시작했다. 유토피아의 법에는 왕의 계승자가 없는 www.acmicpc.net 각 부모에서 자식으로 가는 방향의 간선을 연결해 그래프를 만들고, 위상 정렬을 통해 각 정점의 점수(왕족의 비율)를 매겨 문제를 해결했다. 코드 #include #include #include #include #include #include using namespace std; int n, m; int id_cnt = 0; map name_id; vector adj[200]; vector indegree(..

https://www.acmicpc.net/problem/22959 22959번: 신촌 수열과 쿼리 첫째 줄에 수열의 크기 $N$이 주어진다. ($1 \le N \le 200\,000$) 둘째 줄에는 수열의 원소 $a_1,$ $a_2,$ $\cdots,$ $a_N$ 이 주어진다. ($1 \le a_i \le 10^9$) 셋째 줄에는 쿼리의 개수 $M$이 주어진다. ($1 \le M \le 200 www.acmicpc.net 구간의 최솟값을 저장하는 세그먼트 트리와, 구간의 합을 저장하는 세그먼트 트리를 이용하여 문제를 해결했다. 1번 쿼리의 경우에는 세그먼트 트리의 업데이트를 수행했고, 2번 쿼리의 경우에는 l과 r을 찾아서 해당 구간의 합을 세그먼트 트리를 이용해 구하면 되는데, 이때 l의 경우 l ~..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이분 탐색을 통해 두 공유기 사이가 최소 특정 거리 이상으로 배치해서 공유기를 모두 배치할 수 있는지 판단하는 방법으로 문제를 해결했다. 코드 #include #include #include using namespace std; int n, c; vector x; //두 공유기 사이가 최소 dist 이상으로 만들 수 있는지 확인 bool Solv..