백준 (17) 썸네일형 리스트형 WayInWilderness 경희대학교 2024-2025 ICPC팀팀원 : overnap, penguin1234, jwpassion1 대회 참가2025년The 2025 ICPC Asia Pacific Championship 27위 / 한국 6위 (overnap, jwpassion1, penguin1234) 2025.03.012024년ICPC 2024 Asia Yokohama Regional Engineer Guild Prize (15위) (penguin1234, jwpassion1, overnap) 2024.12.222024 ICPC Seoul Regional Honor (40위 / 한국 35위) (penguin1234, overnap, jwpassion1) 2024.11.23CALICO Fall '24 Gold Brick (16.. 백준 1805번 나무수송 https://www.acmicpc.net/problem/1805 dp[i][j][k] 를 i번 노드를 루트로 하는 서브트리에 대해 목공소를 정확히 j개를 짓고 서브트리의 모든 나무가 i번 노드까지 이동했을때 k개의 나무가 목공소를 거치지 않은 경우의 최소 운반비 로 정할 수 있다.목공소의 여러 조합에 따른 k의 가짓수를 정확히 알수는 없지만 검은돌 트릭에 따라 노드를 합치는데 드는 비용이 생각보다 적기에 시간 안에 돌 수 있다는 계산으로 일단 코드를 짜 보았고 TLE를 받았다. #pragma GCC optimize("Ofast")#include using namespace std;int k;vector>> graph;vector w;vector>> dp;void dfs(int node){ dp[n.. 백준 1517번 버블 소트 https://www.acmicpc.net/problem/1517 i A[j]인 모든 (i, j) 쌍에 대해 A[i]와 A[j]의 위치관계가 바뀌어야 한다. 앞에서부터 순차적으로 오름차순 순서를 유지하며 swap 연산들을 수행하면 불필요한 swap 연산이 발생하지 않고 이때 swap 횟수는 각 수에 대해 자신 이전에 등장한 자신보다 큰 수의 개수이다. 이는 좌표압축 + 세그먼트 트리로 해결할 수 있다. #pragma GCC optimize("Ofast")#include using namespace std;int res = 1;vector tree;void init(){ tree.resize(res);}void update(int t1, int t2, int q, int idx){ if (q .. 백준 3397번 Division Expression https://www.acmicpc.net/problem/3397 괄호가 없는 x1/x2/x3/ ... /xk를 생각해 보자. 분자에는 x1 하나만 있고 다른 수는 전부 분모가 된다.괄호를 이용한 기본적인 식 (x1/x2) / (x3/x4)를 보면 나눗셈의 앞부분에는 영향이 없지만 나눗셈 뒤에 오는 괄호 안의 분수는 역수로 취해져 분자와 분모가 바뀌게 된다. 괄호가 없을때와 비교하면 x3는 그대로 나누어지지만 x4는 곱해지게 된다.우선 괄호를 어디에 두더라도 x1은 분자, x2는 분모에 위치한다는 것을 알 수 있다. 정수를 만드려면 분모의 인수가 적을수록 유리함으로 분모에 곱해지는 수는 최소화 해야한다. x1/(x2/x3/x4/.../xk)를 하면 (x1*x3*x4*...*xk) / x2가 되어 유클리드.. 백준 2813번 매력있는 울타리 https://www.acmicpc.net/problem/2813 두 수의 차이는 (큰수 - 작은수)의 꼴을 가진다.따라서 울타리의 각 판자를 좌우 판자와의 대소관계에 따라 {(자신보다 큰 판자 두개와 인접한다), (자신보다 자신보다 큰 판자 하나와 인접한다), (자신보다 큰 판자 하나, 작은 판자 하나와 인접한다), (자신보다 작은 판자 하나와 인접한다), (자신보다 작은 판자 두개와 인접한다)}의 5가지 상태로 나눌 수 있다.이를 매력도에 미치는 영향으로 변환해보면 {(두번 빼진다), (한번 빼진다), (값이 변하지 않는다), (한번 더해진다), (두번 더해진다)}로 바뀌게 된다. 각 수와 상태들의 구성이 변하지 않고 일대일로 매칭되니 큰수를 더하고 작은수를 빼는것이 최대값임을 알 수 있다. 따리서 .. 백준 22199번 Cat in a tree https://codeforces.com/blog/entry/134665코드포스 블로그를 둘러보다 트리DP에서 노드의 정보를 스몰 투 라지로 합치는 검은돌 트릭이 서브트리의 크기가 아닌 최대 깊이에 비례하는경우 상당히 빨라진다는 글을 보았다. qwerasdfzxcl 님이 말하기로는 시간복잡도가 무려 O(N)이 나온다고 하였다. 최근 팀연습에 나온 요코하마 2023 J번이나(이건 정해가 HLD이다! 검은돌 트릭을 쓰면 1초면 충분하다!) 이번 카이스트 Mock L번 등 최근 자주 사용되는 유형인것 같아 여러 경우에 따른 시간복잡도를 알아두면 꽤나 도움이 될것같다. https://www.acmicpc.net/problem/22199소개된 연습문제 하나가 백준에 있어 풀어보았다. 내가 짠 코드는 deque가 .. 2024 신촌지역 대학생 프로그래밍 동아리 연합 여름 대회 (SUAPC 2024 Summer) Open Contest 후기 대회 링크 8월 월간 향유회(후기) 온사이트 대회장에 도착했는데 등록까지 30분이 남아서 배경을 따기 위해 카페에서 잠깐 대회에 참가했다.문제 푸는동안 선린 후배인 gubshig님을 만나서 근황 이야기도 잠시 나누었다. A번 SWAPC(백준 32158번) - AC - 1시간 6분 12초P와 C를 각각 저장해둔뒤 하나씩 짝을 지었다. #pragma GCC optimize("Ofast")#include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; string S; cin >> N >> S; vector pi, ci; f.. 백준 8872번 빌라봉 https://www.acmicpc.net/problem/8872 8872번: 빌라봉첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. 1 ≤ N ≤ 100,000 0 ≤ M ≤ N-1 0 ≤ A[i], B[i] ≤ N-1 1 ≤ T[i] ≤ 10,000 1 ≤ L ≤ 10,000www.acmicpc.net 일단 각각의 연결된 빌라봉들이 트리형태이니 연결된 빌라봉들마다 한번씩 dfs를 돌려야 할 것 같다.그리고 그 트리가 다른 트리들과 연결될때는 하나의 노드에서만 연결되고 트리에서 그 노드로부터 가장 먼 정점의 거리가 가장 짧게되는 정점을 잡으면 된다.이때 트리마다 나오는 이 거리들을 그 트리의 가중치로 두면 각 트리를 정점으로 하는 큰 트리가 만들어 .. 이전 1 2 3 다음
