-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...
-
[BOJ] 2812 : 크게 만들기
2812 : 크게 만들기 풀이 토막 나며 부서진 나의 여러 기대는 공중에 날려 사라져가고 딱딱한 구름 밑에서 벅찬 무게를 견디며 혼자 그렇게 작아져 갔다 코드 #include <cstdio> int n, k, pos; char s[500005]; int main() { scanf("%d %d %c", &n, &k, &s[0]); pos = 1; for (int i = 1; i < n; i++) { scanf("%c", &s[pos]); while (k && pos && s[pos-1] < s[pos]) { s[pos-1] = s[pos]; s[pos] = 0; k--; pos--; }...
-
[BOJ] 1541 : 잃어버린 괄호
1541 : 잃어버린 괄호 풀이 아무도 얘기하지 않는 몇 해가 쉽게 지나 버리고 휑하니 텅 빈 가슴속으로 눈꽃 송이 내려앉는다 아무리 잠들어도 캄캄한 바람 지날 뿐 어떤 꿈도 만나지 못해 코드 #include <cstdio> int sum, tmp, f, n; char s[55] = {1}; int main() { scanf("%s", s+1); for (int i = 1; s[i-1]; i++) { if ('0' <= s[i] && s[i] <= '9') { n *= 10; n += s[i] - '0'; } else if...
-
[BOJ] 1138 : 한 줄로 서기
1138 : 한 줄로 서기 풀이 사람 마음이 참 생각처럼 되질 않아 쓴웃음에 한 번 더 미련을 삼켜 보곤 해 미워하고 싶은데 그것조차 잘 안 돼 너의 기억은 너무나 찬란해 잠 못 들게 해 코드 #include <cstdio> #include <vector> using namespace std; int n, x, a[12]; vector<int> v; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } v.push_back(n); for (int i = n-1; i >= 1;...
-
[BOJ] 2294 : 동전 2
2294 : 동전 2 풀이 가져가 지독한 그리움 기억 속 널 다시 데러가 난 아무렇지 않은 척 애를 써도 또다시 울컥하고 말아 아직도 난 코드 #include <cstdio> int n, k, t, d[100001]; int main() { scanf("%d %d", &n, &k); for (int i = 1; i <= k; i++) { d[i] = 1e9; } for (int i = 1; i <= n; i++) { scanf("%d", &t); for (int j = t; j <= k; j++) {...