-
[BOJ] 11437 : LCA
11437 : LCA 풀이 naive한 풀이! dfs 먼저 돌려서 각 노드마다 깊이를 구해준 뒤, u, v 두 노드 중 더 큰 노드의 깊이를 끌어 올려준 다음에 두 노드에서 동시에 하나씩 올라가며 같은 노드에서 마주칠 때 까지 올려주면 된다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; const int n_ = 5e4 + 3; int n, m; int dph[n_], pnt[n_]; vector<int> gph[n_]; inline void dfs(int now, int cnt) { dph[now] = cnt++; for (auto...
-
[BOJ] 13306 : 트리
13306 : 트리 풀이 엣지를 제거하면서 union find를 하려면 TLE가 난다. 문제를 거꾸로 생각하자. 원래의 문제는 간선이 모두 이어진 상태에서 하나씩 제거하는 형태이다. 그렇다면 역으로 간선을 다 끊어놓고 쿼리를 뒤에서 부터 돌면 되지 않을까?! 간선을 하나씩 이어주면서 union find를 돌리게 되면 빠르게 답을 구할 수 있다. 발상의 전환이 조금 어려운 문제인 것 같다. 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 2e5 + 3; int n, q; int gph[n_], pnt[n_], q1[n_ * 2],...
-
2017 선린 봄맞이 교내대회 풀이
2017 선린 봄맞이 교내대회 풀이 문제 링크: https://www.acmicpc.net/contest/view/222 뭔가 야심차게 HARD 난이도(교내대회 기준)로 낸 문제들이 여럿 있었는데 생각치 못하게 엄청 쉽게 풀려서 당황스러웠다 ㅠㅠ A. 욱제는 효도쟁이야!! 14487 : 욱제는 효도쟁이야!! 풀이 각 마을간의 이동거리가 주어지고, 모든 마을을 순회할 때 그 이동거리의 합을 최소로 만드는 문제이다. 모든 이동거리의 합에서 최대 이동거리를 빼주면 된다. 코드 #include <stdio.h> int n, tmp, sum, i, a; int main() { scanf("%d", &n); for (i = 0; i < n; i++)...
-
2017 선린 봄맞이 교내대회 안내
2017 선린 봄맞이 교내대회 안내 안녕하세요! 대회의 세부사항에 대해서 안내 해드립니다. 일시: 2017년 4월 9일 일요일 14:00 ~ 19:00 5시간 장소: acmicpc.net 후원: 스타트링크 상품: 1등 치킨 기프티콘 출제: wookje, leehun456 한글, 12문제, 3인 이하의 팀전 Open Contest 동시 운영 4월 6일 오후에 대표자 이메일로 팀 전용 계정을 발송해드립니다. 반드시 확인하시고 4/7~4/8 사이에 이 링크에 있는 2017 선린 봄맞이 교내대회 예비소집에 참여하셔서 채점환경 등을 확인해주시기 바랍니다. 아래의 테이블은 참가자 정보입니다. 누락되거나 잘못된 정보는 연락해주시면 즉시...
-
[BOJ] 11052 : 붕어빵 판매하기
11052 : 붕어빵 판매하기 풀이 dp[i] = 붕어빵 i개를 팔았을 때의 최댓값 dp[i] = i-j번째 최댓값 + j개 세트의 가격 코드 #include <stdio.h> int n, i, j, a[1001], dp[1001]; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) if (dp[i] < dp[i - j] + a[j]) dp[i] = dp[i - j] + a[j];...