https://www.acmicpc.net/problem/9874 9874번: Wormholes Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 n; for (int i = 0; i > x >> y; point.push_back(make_pair(x, y)); } //x축 기준으로 정렬 sort(point.begin(), point.end()); // 해당 위치에서 +x 방향으로 이동하면 도달하는 위치를 연결한다 for (int i = 0; i < point.size(); i++) { for (int..

https://www.acmicpc.net/problem/27882 27882번: 가희와 지하철역 저장 시스템 2 가희는 멍멍철도공사에서 관리하는 n개의 지하철역 정보를 보기 위해, 지하철역 관리 시스템을 운영하고 있습니다. 이 시스템에서, n1번 노드에서 n2번 노드로 데이터를 보내는 전송 시간은 아래 www.acmicpc.net 기존 입력으로 부여된 node_id의 범위(1~10^9)는 너무 큰 반면, 전체 노드 개수의 범위(1~300)는 작아서, node_id의 크기 순으로 새로운 id(n_id)를 부여했다. 이를 이용해 노드 간 그래프를 만들어, 다익스트라를 통해 각 요청 노드와 가장 가까운 캐시 노드와 거리를 구하고, 또한 각 캐시 노드와 버킷노드와 최단 거리를 구했다. 그리고 저장해 놓은 값을..

https://www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 점들 사이의 비용이 c이상이면, 해당 점들 사이에 간선(파이프)을 추가해서, 만들어진 간선을 이용해 최소 ..

https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 어항을 상태 2차원 배열에 bowl에 표시하였고, 각 열에 대한 높이를 height에 저장해 놓았다. 물고기 수가 가장 적은 어항에 물고기를 한마리 넣기, 어항을 쌓기, 물고기의 수 조절하기, 어항을 바닥에 일렬로 놓기, 가운데 중심으로 어항 쌓기를 함수로 분리하여 문제를 해결했다. 코드 #include #include #include #include #include using namespace ..

https://www.acmicpc.net/problem/27114 27114번: 조교의 맹연습 첫 번째 줄에 각각 좌로 돌아, 우로 돌아, 뒤로 돌아에 들어가는 에너지를 나타내는 세 정수 $A, B, C$와 사용하고자 하는 총 에너지양을 나타내는 정수 $K$가 공백으로 구분되어 주어진다. $(1\leq A,B www.acmicpc.net cache[남은 에너지][현재 방향]에 남은 에너지를 모두 다 쓰고, 처음 방향으로 돌아가는 최소 연산 횟수를 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다 코드 #include #include #include using namespace std; vector e; int k; vector cache(1000005, vector(4, -1)); //[남은 에너지]..

https://www.acmicpc.net/problem/16965 16965번: 구간과 쿼리 N개의 쿼리가 주어졌을 때, 쿼리를 수행해보자. 쿼리는 총 2가지 종류가 있고 아래와 같다. 가장 처음에 집합에는 아무것도 없다. 1 x y (x < y): 새로운 구간 (x, y)를 집합에 추가한다. 구간의 크기 www.acmicpc.net 새로운 구간을 집합에 추가하는 쿼리일 때, 이전에 들어왔던 구간들과 이동이 가능한지 확인하여 만약 이동이 가능하다면 그래프로 연결했고, 구간 사이 이동이 가능한지 확인하는 쿼리일 때는 만들어 놓은 그래프를 이용해 두 구간 사이 탐색으로 도달이 가능한지 확인해서 문제를 해결했다. 코드 #include #include #include using namespace std; in..