반응형 전체 글53 백준 7869번 : 두원 (C/C++) 백준 7868번 두원 3가지 경우가 있다. 한원이 한원을 포함하는 경우 안겹치는 경우 일부분이 겹치는 경우 1의 경우에는 작은원의 넓이를 출력하고, 2의 경우는 0을 출력한다. 3의 경우는 코사인 공식을 이용하여 세타 값을 구해서 넓이를 구해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #define fio() \ ios_base::sync_with_stdio(0); \ cin.tie(0) using namespace std; typed.. 2023. 5. 16. 백준 16437번 : 양 구출 작전 (C/C++) 백준 16437번 주어진 문제상황은 DAG이고, 최종 목적지가 1번이다. 따라서 위상 정렬을 적용해볼 수 있다. 늑대의 수를 음수로 표현하고, 양의 수를 양수로 표현한다. 문제에서 늑대들은 이동하지 않는다고 했으므로 노드가 양수가 되었을때, 다음 노드로 넘겨주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #define fio() \ ios_base::sync_with_stdio(0); \ cin.tie(0) using namespace std; typedef long long ll.. 2023. 5. 9. 백준 2533번 : 사회망 서비스(SNS) (C/C++) 백준 2533번 최소 얼리 어댑터의 수를 구하는 문제이다. 전형적인 트리dp문제라고 볼 수 있다. 이문제를 풀기 위해서는 트리는 트리로 구성되어있다는 개념을 이용해야한다. 우선 k=1을 얼리 어댑터, k=0인 경우를 얼리 어댑터가 아닌 경우라고 할때, dp 배열을 아래와 같이 정의한다. dp[n][k] : n이 k이고, n을 루트로하는 서브트리의 최소 얼리 어댑터의 수 1. k=1일때, 자식 노드들이 1이여도 되고, 0이여도된다. n의 모든 자식 노드를 nx라고 할때, 다음이 성립한다. 2. k=0일때, 모든 자식 노드들이 1이여야만 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34.. 2023. 5. 9. 백준 13511번 : 트리와 쿼리 2 (C/C++) 백준 13511번 주어진 쿼리에 대해 답하는 문제이다. 백준 1761번: 정점들의 거리 백준 11438 : LCA 2 아래 배열을 정의한다. depth[x] : 루트로부터 정점 x까지의 거리 lev[x] : 루트를 기준으로 정점x의 레벨 pa[x][i] : 정점 x의 2^i번째 부모 우선 dfs탐색을 통해 depth, lev, pa배열을 채운다. l = lca(u, v)라고 할때, 쿼리1은 (depth[u]-depth[l])+(depth[v]-depth[l])로 구할 수 있다. 쿼리 2는 u부터 시작하여 k번 탐색을 진행하여야하는데 매 쿼리마다 k번의 탐색을 하면 시간초과가 날 것이다. 효율적인 풀이를 위해 경우를 나눈다. 1. k < lev[u]-lev[l]+1 인 경우 : u의 k-1번째 부모를 구한.. 2023. 5. 6. 백준 25638번 : 트리와 경로 개수 쿼리 (C++) 백준 25638번 q개의 쿼리에 대해 정점 u를 지나는 경로의 개수를 구하는 문제이다. 정점 u에 대해서 다음과 같이 2개의 트리로 쪼개 진다고 가정해보자. 트리 x에대해 빨간점의 개수를 red[x], 파란점의 개수를 blue[x]라고 정의할때, 경로의 개수는 red[1]*blue[2] + blue[1]*red[2]개이다. 따라서 각각의 트리에 대해 red[x], blue[x]를 구하는 것이 핵심이라고 할 수 있다. 그러나 모든 쿼리마다 각각의 트리의 red[x], blue[x]를 계산하면 시간 초과가 날 것이 뻔하다. 보다 효율적인 방법을 생각해보자. 우선 풀이의 편의성을 위해 루트를 1로 설정하겠다. 그리고 임이의 정점u를 아래 그림으로 나타내었다. r[x], b[x]를 아래와 같이 정의해주자 r[x.. 2023. 5. 5. 이전 1 ··· 6 7 8 9 다음 반응형
