미분당한 적분상수

https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net tree dp를 이용해 푼 문제이다. 우수 마을을 선정하는 조건은 다음과 같다. '우수 마을'로 선정된 마을 주민 수의 총합을 최대로 해야 한다. '우수 마을'끼리는 서로 인접해 있을 수 없다. '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다. dp테이블에 우수 마을인지 아닌지를 같이 기록하기 위해, 다음과 같은 dp테이블을 정의한다. dp[ i ..

https://www.acmicpc.net/problem/25690 25690번: 트리를 복잡하게 색칠하는 최소 비용 0번 정점을 white, 1번 정점을 white, 2번 정점을 white, 3번 정점을 black, 4번 정점을 white, 5번 정점을 white, 6번 정점을 white, 7번 정점을 white로 색칠하는 비용 220이 정답이다. www.acmicpc.net tree dp를 사용하여 푼 문제이다. 트리를 흰색 또는 검은색으로 칠할 때 각각 필요한 비용이 있고, 이웃한 정점을 흰색 검은색 또는 흰색 흰색으로 칠할 때, 트리의 모든 노드를 색칠하는 최소 비용을 구하는 문제이다. 정점의 상태가 흰색 또는 검은색일 수 있으니, dp 테이블을 2차원으로 정의하자. dp[ i ][ j ] : i..

https://www.acmicpc.net/problem/12978 12978번: 스크루지 민호 2 구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을 www.acmicpc.net tree dp를 이용하여 푼 문제이다. 문제에 약간 함정이 있는데, 문제를 가볍게 읽고 문제를 푼다면, 경찰서가 인접한 정점들을 감시하고 감시하지 못하는 정점이 없게 문제를 풀기 시작하는 대참사가 벌어질 수 있다. 문제에서 요구한 것은 감시하지 못하는 '도로'들과 도시들을 없게 하는 것이다. 따라서 그냥 경찰서와 경찰서의 최소 거리가 2 이상이 아니게 답을 구해주면 된다. dp테이블에 상태값까지..

tree dp 이전에 일반적인 dp에 대해 살짝 이야기하고 tree dp로 넘어가려 한다. 먼저 어떤 문제를 dp로 풀기 위해서는 다음 3가지 조건을 만족해야 한다. 1) 큰 문제를 작은 문제로 나눌 수 있다. 2) 충분히 작은 문제는 쉽게 풀 수 있다. 3) 작은 문제들의 답에서 큰 문제의 답을 구할 수 있다. 이를 만족하는 문제일 때, 작은 문제에서 구한 답을 이용해 큰 문제의 답을 구하는 게 일반적인 dp문제이다. 이제 tree dp에 대해 살펴보자. 트리는 '트리 안에 또 다른 트리(서브 트리)가 존재한다.' 라는 특징을 가지고 있다. 이는 위에서 언급한 문제를 dp로 풀기 위한 조건 1과 흡사하다. 따라서 tree dp의 dp 테이블은 이런 형태를 가진다. dp[ i ] : i를 루트 노드로 하..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 인접한 정점들의 관계에 따라 tree dp를 이용하여 푸는 문제이다. 만약 현재 정점을 선택하지 않는다면, 다음 정점은 선택해야한다. 만약 현재 정점을 선택하면, 다음 정점은 선택해도 안해도 된다. 이를 이용하여 dp테이블을 채워가며 답을 구한다. dp테이블을 다음과 같이 정의하자. dp[ i ][ j ] : i번째 정점을 선택할 때 j = 1, 선택하지 않을 때..

https://www.acmicpc.net/problem/25515 25515번: 트리 노드 합의 최댓값 노드 0, 노드 1, 노드 2, 노드 4, 노드 5, 노드 6, 노드 7을 방문하는게 정답이다. www.acmicpc.net tree dp를 통해 해결하는 문제이다. 만약 현재 정점의 비용을 cur_cost, 다음 정점의 비용을 next_cost라 하면 현재 정점에서의 최댓값은 다음이 성립함을 알 수 있다. cur_cost = max(cur_cost+next_cost, cur_cost) (비용이 음수 일 수도 있기 때문에 최대를 선택해주어야 한다) #include using namespace std; #define N 100100 typedef long long ll; vector tree[N]; l..

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net tree dp의 기본 문제이다. 그냥 dfs를 통해 dp값을 누적하며 누적한 값을 계속 다음 값에 더해주기만 하면 된다. #include using namespace std; typedef long long ll; int n,r,q; int dp[100100]; bool visited[100100]; vector tree[100100]..

https://www.acmicpc.net/problem/24232 24232번: 망가진 나무 첫째 줄에 뒤집어야하는 간선을 $N-1$자리 이진수로 출력한다. 왼쪽에서 $i$번째 비트는 $i$번째 간선을 뒤집어야 하면 1, 아니면 0이다. 이진수에 등장하는 1의 개수가 최소가 되도록 해야 한다. www.acmicpc.net 방향을 가진 그래프가 주어진다. 방향성을 없애면 트리가 된다는 특징이 있다. 임의의 한 정점에서 다른 모든 정점으로 갈 수 있게 하려면 간선의 방향을 바꿔주어야 하는데, 이때 방향을 바꾸어야 하는 최솟값을 구하는 문제이다. 이 문제를 풀려면 모든 정점에 대해 방향을 바꿔주어야 하는 횟수 (이하 비용으로 대체하겠다)를 알아야 할 필요가 있다. 그러려면 모든 정점 n개에 대해 dfs를 진..

https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 서로 이웃하지 않는 정점들의 가중치 합의 최대를 구하고 그것을 역추적하는 문제이다. 가중치 합의 최대만을 구하라 하면 다른 골드 3 tree dp 문제와 다름이 없으므로 그것을 역추적하는 방법에 대해서만 대략적인 설명을 할 생각이다. 처음 tree dp를 진행할 때, 다음 노드를 선택한 경우와 선택하지 않은 경우 중 최대를 골라 저장하는 부분이 있다. 그때 역추적을..