문제링크 : https://www.acmicpc.net/problem/25516 25516번: 거리가 k이하인 트리 노드에서 사과 수확하기 n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 모든 간선의 길이는 1이다. 트리 T의 각 정점에는 사과가 0개 또는 1개 놓여있다. 루 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, K, p, c, result; vectorv[100001]; int arr[100001]; void dfs(int node, int dist) {..
문제링크 : https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, u, v; vectorgraph[501]; bool visited[501]; bool dfs(int cur, int post) { visited[cur] = true; for(i..
문제링크 : https://www.acmicpc.net/problem/13116 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, A, B; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; while(T--) { cin >> A >>..
문제링크 : https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int K, Q; ll N, x, y; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> ..
문제링크 : https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, u, v; int parent[50001]; int depth[50001]; vectornode[50001]; void dfs(int n, int p) { parent[n] = p; //부모..
문제링크 : https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, N, A, B, X, Y; int parent[10001]; int visited[10001]; int dfs(int n) { if(visited[n..
문제링크 : https://www.acmicpc.net/problem/25511 25511번: 값이 k인 트리 노드의 깊이 n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 간선에는 가중치가 없다. 트리 T에 있는 각 정점에는 서로 다른 값이 부여된다. 트리 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, K; int arr[100001]; int parent[100001]; int dfs(int n, int cnt) { if(n==0) return cnt; //루트 ..
문제링크 : https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, N, M; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; while(T--) { cin >> ..
문제링크 : https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, s, e; vectort[1001]; int dist[1001]; int bfs(int s, int e) { queueq; q.push(s); dist[s]=0; while(!..
문제링크 : https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, N, M; int arr[21]; int dp[10001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; w..
문제링크 : https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, remove_node, root, result; vectort[51]; //트리 int visited[51]; //방문처리용 void dfs(int node) { visited[node]=1; b..
문제링크 : https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; string s1, s2; int dp[4001][4001]; int result; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> s1 >..
문제링크 : 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 #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, R, Q; int U,V,u; int dp[100001]; vectorv[100001]; bool visited[100001]; int f..
문제링크 : https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, T, K, S; int dp[10001]; int dp2[10001]; int main() { ios_base::sync_with_stdio(0); cin...
문제링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int dp[100001][3]; const int MOD = 9901; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[1][0] = 1; //ox dp[1][1] = 1; //xo dp[1][2] = 1; //xx for(int i=2; i OX or XX 가..