중학교때 잠깐 봤었던거 같은 문제 [원석방 산하 폐수방] 1일차 셋 div 2 A번이다. https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 일단 간단한 그림을 그려보든지 해서 알수 있는 정보는 벽장문을 옮길때, 횟수는 그냥 A번 벽장을 B번 벽장으로 옮기고자할때 abs(A-B) 이다. 사이에 C번벽장이 있더라도 이는 동일하다. 여기서 좀 이상한 사고를 거쳐서, 브루트포싱하자는 의견에 도달했다. 벽장 두개가 기본적으로 주어져있고, 열려있는 벽장..

오늘은 세그 미는날~~ 평범한 최솟값 세그가 아니여서 좀 고생했다. www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 이 문제의 핵심은 세그트리가 반환해주는 값이 구간 내의 히스토그램 값의 최솟값 이 아니라, 히스토그램이 최솟값을 가지는 곳의 인덱스값이다. 이를 위해 세그트리를 살짝 수정해 준 뒤에, 구간에서의 최대값을 찾을때에는 분할정복을 이용해주었다. 분할을 할때는 반드시 딱 절반에서 나누는 것이 아..

프림 / 크루스칼 알고리즘을 사용하면 쉽게 해결할 수 있다. 나는 크루스칼 알고리즘을 사용했다. www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘의 기본적인 구현을 묻는 문제 더보기 #include using namespace std; typedef long long int ll; struct line{ int s; int e; int w; }; vector g; int parent[12345] ..

다익스트라 연습 (2) www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 각각의 좌표를 노드로, 각각의 좌표에 있는 도둑루피의 수를 가중치로 보자면 가중치합을 최소로 해서 (0,0) 에서 (n-1,n-1) 까지 이동하는 평범한 다익스트라 문제가 된다. 더보기 #include #define INF 123456789 #define st first #define nd second using namespace std; int arr[150][150]..

다익스트라 연습중 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 초(시간) 에 해당하는걸 간선의 가중치로, 각각의 점 위치를 노드로 보면 그래프에서의 N번 노드에서 K번 노드까지의 가중치의 최소값을 구해주면 되므로 다익스트라로 해결할 수 있다. 단순한 다익스트라에, 간선조건조차 그리 어려운 편이 아니므로 자세한 설명은 생략해도 괜찮을 것 같다. 더보기 #include #define INF 123456789 using nam..

누가봐도 다익스트라같이 생긴 문제이고, 실제로 다익스트라를 빠삭하게 이해하고 있다면 해결할수 있는 문제였다. www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라는 탐색 도중에서 의도적으로 최단경로가 아닌 경우를 배제하는데, 이 배제되는 경로들을 전부 잘 저장해두고 정리해주면 된다. if(ans[next].size() < k){ pq.push({-(dist+dis), next}); ans[next..