Problem solving/BOJ29 [BOJ] 1774. 우주신과의 교감 (C++) 문제 2차원 좌표에서 이미 연결된 통로가 존재한다. 모든 우주선끼리 연결해야하는데, 추가로 연결해야 할 통로의 길이 합이 최소가 되도록 통로 연결하기 생각할 것 중복된 데이터가 들어갈 수 있음 반례 4 2 1 1 3 1 2 3 4 3 1 4 4 1 정답 : 4.00 union연산을 할 때만 count를 올리도록 코드를 변경했더니 정답이었다 코드 #include #include #include #include #include using namespace std; struct Edge { int start, end; double cost; }; struct cmp { bool operator()(Edge &e1, Edge &e2) { return e1.cost > e2.cost; } }; int find(i.. 2023. 7. 28. [BOJ] 1647. 도시 분할 계획 (C++) 문제 마을은 N개의 집과 M개의 길로 이루어져 있다. 두 개의 분리된 마을로 분할하려고 할 때, 각 분리된 마을 안에 있는 임의의 두 집 사이에는 경로가 항상 존재해야 한다. 나머지 길의 유지비 합의 최솟값은? 생각할 것 모든 마을을 최소값으로 연결하고 가장 긴 하나의 길만 분리하자 크루스칼을 N-2번만 실행하기 코드 #include #include #include using namespace std; struct Edge { int cost, start, end; }; struct cmp { bool operator()(Edge &e1, Edge &e2) { return e1.cost > e2.cost; } }; int find(int a, vector &parent) { if (parent[a] ==.. 2023. 7. 27. [BOJ] 14938. 서강그라운드 (C++) 문제 각 지역이 일정한 길이의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수 생각할 것 예은이의 출발 위치가 정해져 있지 않으므로 플로이드 워셜을 사용해보자! 각 지역에서의 거리를 모두 구한 뒤, 각 지역에서 탐색할 수 있는 지역만큼 아이템을 더해준다 코드 #include #include #define INF 1e9 using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, r; cin >> n >> m >> r; vec.. 2023. 7. 25. [BOJ] 13549. 숨바꼭질 3 (C++) 문제 수빈이는 점 N, 동생은 점 K에 있다. 수빈이가 X일 때 걸으면 1초 후에 X-1 or X+1로 이동하고 순간이동하면 0초 후에 2*X의 위치로 이동한다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간은? 생각할 것 음수로도 갈 수있고, 출발지와 도착지가 정해져있으므로 벨만 포드를 써보려 한다 하지만 시간 초과가 발생했다. 다익스트라를 사용해보자 범위만 -연산이 일어나고, 시간은 줄어들지 않기 때문에 다익스트라를 사용해도 될 것 같다! 코드 벨만 포드 - 시간 초과 발생 #include #include #define INF 1e9 using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N.. 2023. 7. 25. 이전 1 2 3 4 5 6 7 8 다음