본문 바로가기

전체 글

9367 관리 난항 아.. 시뮬레이션..... 못풀었다. 어렵다 . #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() #define NOT_USING -1 #define INCONSISTENT -1 using namespace std; using i64 = long long int; using ii = pair; using iis = pair; using ii64 = pair.. 더보기
20390 완전그래프의 최소 스패닝 트리 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii = pair; using iis = pair; using ii64 = pair; using iii = tuple; struct Edge { i64 u, v, d; }; i64 par[10005]; i64 f.. 더보기
16493 최대 페이지 수 입력이 작아서 모든 경우의 수를 다 구해도 되겠다 싶었다. 비트마스크로 모든 경우를 다 구해서 페이지 합산, 일 합산을 구한다. 일 합산이 기한보다 작은 경우 최대 페이지 수를 구한다. 끝~ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii = pair; .. 더보기
14621 나만 안되는 연애 그래프의 최단 거리를 구해야 하기 때문에 MST를 사용하면 되겠다 싶었다. 그런데 MST를 일년 전에 공부했고 자료도 정리해놓지 않아서.... 다시 이해하는데 오래 걸렸다. 그리디하게 가장 edge를 구해놓고 가장 짧은 것부터 뽑아서 계산한다. Union Find로 해당 간선이 이미 계산된 간선인지 확인한다. 코드는 1. 학교 입력 받으면서 유파 초기화 2. 여-남 경우에만 간선을 추가한다 3. 간선을 오름차순으로 정렬한다 -> 그리디하게 가장 짧은 것부터 뽑기 위해서 4. 가장 짧은 길이부터 뽑아서 더한다, 간선을 몇 개 더했는지도 계산한다 5. 간선이 n - 1개가 아닌 경우 노드를 전부 확인 안 했으니 -1을 출력한다 #include #include #include #include #include .. 더보기
4095 최대 정사각형 부분합..? 생각이 들었는데 아무리봐도 부분합 문제는 아니었다. dp였다. 하나의 모서리를 기준으로 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 를 확인한다. 이거 이전에 42에서 푼 문제인데? 익숙하다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long in.. 더보기
7662 이중 우선순위 큐 처음에 큐를 두 개 사용해서 풀면 되겠다 싶었다. 그런데 음... 우선순위 큐의 bottom을 빼오는 방법은 없었다. 고민하다가 해결하지 못해 다른 사람 풀이를 봤다. 큐에 값이 없는지 map을 사용해서 따로 관리를 했다!! 만약 삭제된 값이면 0으로 처리를 했다. 조금 찜찜한 점은 요 부분이다. while (!pqMin.empty() && mp[pqMin.top()] == 0) pqMin.pop(); 만약 우선순위 큐가 가득 차있어서 n개 요소가 들어있다고 하면 n번 * map nlogn번 해서 터지지 않나? 싶다. 아 map은 logN이었다. 해결~~ #include #include #include #include #include #include #include #include #include #in.. 더보기
1374 강의실 1. 강의를 시작시간과 끝 시간 기준으로 정렬한다 2. 강의실 우선순위 큐를 만든다 3. 만약 현재 진행중인 강의와 겹친다면 강의실 + 1 4. 겹치지 않는다면 앞선 강의를 pop 하고 현재 강의를 넣는다 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii .. 더보기
18788 Swapity Swap 풀려고 했었는데 못 풀었다. 생각난 개념은 중간에 반복되는 걸 센 다음 % 해서 구해야겠다 싶었다. 그런데 나머지 연산으로 결과 계산하는게 제대로 안 됐고 결국에는 포기했다. 계속 뭐가 문제인지 모르니깐 문제를 쳐다보기도 싫었다. 어쩌겠어. 다른 사람 풀이를 참고해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace s.. 더보기