-
[BOJ] 11438 : LCA2
11438 : LCA2 풀이 이번엔 naive가 아닌 풀이! 이전의 naive한 풀이에서, 우리는 최악의 경우에 n번의 노드를 하나씩하나씩 올라가야했다. 하지만 이를 log(n)으로 줄일 수 있다! pnt[i][j] = i번 노드의 2^j번째 조상으로 두고 풀면 된다. 트리의 깊이를 구할 때 2^j번째 조상을 구해두자. tmp = anc[i][j-1]일 때, anc[i][j]는 anc[tmp][j-1]과 같다. 즉, i의 2^j번째 조상은 2^(j-1)번째 조상의 2^(j-1)번째 조상과 같다는 의미이다. i의 2^3=8번째 조상은 2^2=4번째 조상의 2^2=4번째 조상과 같다. naive한 코드에서 2^j를 도는 동작만 추가해주면 어렵지 않게(?) 훨씬 빠르게(!)...
-
[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];...
-
[BOJ] 1110 : 더하기 사이클
1110 : 더하기 사이클 풀이 do while 처음 써봤다 ㅋㅋ 코드 #include <stdio.h> int main() { int n, m, c = 0; scanf("%d", &n); m = n; do { c++, m = (m % 10) * 10 + (m / 10 + m % 10) % 10; } while (n != m); printf("%d", c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조,...
-
[BOJ] 2262 : 토너먼트 만들기
2262 : 토너먼트 만들기 풀이 큰 수가 많이 자주 올라갈 수록 합은 크게 나온다. 그렇다면 가장 큰 수 부터 묶어주면 된다! 코드 #include <stdio.h> int max(int a, int b) { return a > b ? a : b; } int n, i, j, a[257], ans; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i = n; i > 1; i--) { for (j = 1; j <=...
-
[codeforces] #403 div1 A (div2 C)
#403 div1 A. Andryusha and Colored Balloons 풀이 이전 노드의 색, 이번 노드의 색에 대한 정보를 가지고 dfs를 돌리면 해결할 수 있다. 추가로, (가장 큰 차수)+1만 가지고 최소로 색칠할 수 있다. 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 2e5 + 10; int n, ans, col[n_]; vector<int> gph[n_]; void dfs(int prv, int cur) { int i = 1; for (auto nxt : gph[cur]) { if (col[nxt]) continue; while (col[prv] == i || col[cur]...
-
[codeforces] #403 div2 B
#403 div2 B. The Meeting Place Cannot Be Changed 풀이 코포 문제는 처음 풀이한다! (두근두근) 이분 탐색을 돌리면 쉽게 해결할 수 있다. 만나는 시간을 mid로 두면, n*log(최대차이)이므로 제한시간에 맞게 돌릴 수 있다. 각각의 좌표 x[i]를 돌면서 mid에 갈 수 있는 max_left, min_right를 구한다. max_left <= min_right면 mid에 만날 수 있다. 왜 그런지는 그림판에 대충 선 몇 개 그려보면 직관적으로 이해 될 것이다. (아마?) AC 받긴 했는데 저렇게 짜도 실수 오차 안 나는지는 모르겠다 (…) 코드...