본문 바로가기

백준

14615 Defend the CTP!!! 1. bfs로 시도했다 -> 시간초과 2. 한번 확인한 경우는 값을 저장해놓으면 빨라지지 않을까? -> 시간초과 3. cin으로 빠른 입출력을 사용하면? -> 시간초과 3진 시간초과로 다음 문제로 넘어갔다. #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.. 더보기
24778 Cracking The Safe 많은 고민을 했는데도 결국 생각해내지 못했다.. 그런데 언젠가 푼 적이 있는 것 같다? 생각해보니 십자뒤집기 문제와 비슷했다. 경우의 수가 얼마 없으니 모든 뒤집는 경우를 다 구해보고 풀면 되겠다 싶었다. https://burningjeong.tistory.com/616 10472 십자뒤집기 어렵다.. 예시 직접 구해보려다가 최소 3번도 못하고 있다ㅋㅋㅋ 3*3이라 전부 구해도 될 것 같은데? 그런데 전부 구하는 방법도 모르겠다. -- 아 문제를 덜 읽었다. 흰색 보드를 클릭해서 입력으 burningjeong.tistory.com 이처럼 9개밖에 안 될 때는 모든 경우로 문제를 풀 수 있다는 걸 떠올려보자. 그런데 이전 문제 풀 때와 다른 점이 있었다. 바로 0, 1로 이루어진 게 아니라 0, 1, 2,.. 더보기
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.. 더보기

티스토리툴바