https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 맥도날드들의 위치와, 스타벅스들의 위치에서 다익스트라 알고리즘을 이용하여 각 정점까지 최단거리 탐색을 해 나아가면서, 각 정점마다 맥도날드에서 해당 정점까지 최소거리, 스타벅스에서 해당 정점까지 최소거리를 구한 뒤, 각 정점을 확인해서 문제를 해결했다. 코드 #include #include #include #include #include usi..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 주어진 모눈종이를 둘러싸는 바깥의 행과 열이 추가된 공간이 있다고 가정하고, 그 공간의 위치들부터 공기가 시작되어 공기가 전파되는 위치를 표시해 놓고, 각 치즈의 위치와 접촉하는 부분에서 공기가 전파된 위치가 2개 이상 있는지 확인하는 방법으로 치즈가 지금 녹는지 확인해서 문제를 해결했다. 코드 #include #include #include #include using namespac..

https://www.acmicpc.net/problem/15823 15823번: 카드 팩 구매하기 첫 줄에는 두 개의 자연수 N과 M이 공백으로 구분되어 주어진다. N은 상점에 진열된 카드의 수이며 M은 주띵이가 구매해야 할 카드 팩의 수다. 이후 두 번째 줄에는 총 N개의 나열된 카드에 대한 www.acmicpc.net 이분탐색을 이용해서 특정 수량의 카드팩을 구성할 수 있는지 확인하는 방법으로 카드팩을 구성할 수 있는 최대 수량을 구했다. 이때, 특정 수량의 카드팩을 구성할 수 있는지 확인하는 방법은, 투 포인터를 이용해 카드 목록을 확인해 보며 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n, m; vector..

www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 다익스트라 알고리즘을 이용해 문제를 해결했다. 주의해야 될 점은 현재 위치까지 총비용뿐만 아니라, 현재까지 가장 싼 주유소 가격도 고려해야 된다는 점이다 그래서 there로 갈 때 here까지 주유소 중 가장 싼 주유소에서 기름을 넣은걸로 한다. 코드 #include #include #include #include #include #include using namespace std; i..

https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net BCC(이중 연결 요소, 이중 결합 요소), 단절선을 이용해서 문제를 해결했다. 코드 #include #include #include using namespace std; int v, e; vector adj[100005]; vector visited(100005, 0); vector node_id(100005, 0); int node_id_cnt = 0; vector..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 날짜별로, 해당 날짜가 마감인 날의 과제 점수들을 저장해 놓고, 마감일이 큰 해당 날짜부터 역순으로 확인해 나아가면서 해당 날짜가 마감일인 점수들을 우선순위 큐에 넣고 우선순위 큐에서 가장 큰 점수를 추출해서 해당 과제를 수행해 나아가는 방식으로 문제를 해결했다. 마감일이 큰 날짜부터 확인하므로, 이전에 확인한 마감일에서 우선순위 큐에 넣어둔 것들은 현재 마감일에도 해결할 수 있는 과제가 되는 것이다. 코드 #include #include ..