https://www.acmicpc.net/problem/17398 17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 어떤 간선이 제거가 될지 알고 있으므로 제거가 안 되는 간선들은 일단 연결한 뒤 마지막으로 잘라지는 간선부터 확인하고 연결하는 방식으로 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n, m, q; vector parent(100001); vector rank_size(1000..

https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net k가 파란색 간선을 최소로 쓰는 스패닝 트리의 파란색 간선의 개수와 파란색 간선을 최대로 쓸 때 스패닝트리의 파란색 간선의 개수 사이라면 파란색 간선이 k개인 스패닝 트리를 만들 수 있다는 것을 이용하여(파란색 간선을 최소로 쓸 때와 최대로 쓸 때에서 간선을 바꿔가며 파란색 간선을 k개로 쓸 때를 만들 수 있을 때) 문제를 해결했다. 파란색 간선을 최소로 쓰는 스패닝 트리는 파란색 간선에 ..

https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 다익스트라를 이용하여 문제를 해결하였는데, 늑대의 경우 [빠르게 갈 때인지 느리게 갈 때인지(1:빠르게, 0:느리게)][위치]를 고려하여 문제를 해결했다. 그래서 늑대의 경우 우선순위 큐를 priority_queue pq; //((-비용,위치),빠르게 갈 때인지 느리게 갈 때인지(1:빠르게, 0:느리게)) 로 만들어서 문제를 해결했다. 코드..

https://www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net 차에서 주차장으로 연결되는 그래프를 만들고 이분 탐색을 통해 최소 거리를 구했다. 해당 거리 안에 모든 차가 주차 가능한지 확인하는 것은, vector parked_car(251, 0); ([주차번호] = (주차된 차 번호)) 를 통해 주차된 차를 저장하고, 각각의 차를 확인할 때마다 vector this_selected_car(251, 0); ([차번호] = (해당 차를 이번 선택에서 주차장을 ..

https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 트리DP를 이용하여 문제를 해결했다. 해당 노드의 위치가 멘토일 때와 멘토가 아닐 때를 고려하여 문제를 해결하였는데, here가 멘토일 때는 there(자식 노드)중 하나는 멘티로 선택되어야 하는데 이때 here의 자식 노드(there)들 중 가장 효과적인 자식 노드를 뽑아 멘티로 고른다. 코드 #include #include #include #include usin..

https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 다이나믹 프로그래밍을 통해 문제를 해결했는데, 이때 위치뿐만 아니라 해당 위치에서 어떤 방향으로 가는지까지 저장하여 문제를 해결했다. 로봇은 위쪽으로 움직일 수 없다는 것과, 한번 탐사한 지역은 탐사하지 않는 것을 이용하여 왼쪽 이동일때 (다음 이동은 왼쪽 또는 아래쪽 이어야 된다), 오른쪽 이동일때 (다음 이동은 오른쪽 또는 아래쪽 이어야 된다), 아래쪽 이동일때 (다음 이동은 왼쪽, ..