본문 바로가기

BOJ

 (55)
[BOJ 20968] Group Photo https://www.acmicpc.net/problem/20986 20986번: Group Photo At the end of a training camp, a group photo is taken with the N participants.The participants are numbered from 1 to N, in order of height. The height of the participant h is h (1 ≤ h ≤ N). The participants stand on the stairs for the photo. There are www.acmicpc.net Tag : dynamic programming, prefix sum 문제요약 수열 \(A\)의 인접한 두 원소들을 swap해가면..
[BOJ 17927] Counting Greedily Increasing Supersequences https://www.acmicpc.net/problem/17927 17927번: Counting Greedily Increasing Supersequences Given a permutation $A = (a_1, a_2, \dots, a_N)$ of the integers $1, 2, \dots, N$, we define the greedily increasing subsequence (GIS) in the following way. Let $g_1 = a_1$. For every $i > 1$, let $g_i$ be the leftmost integer in $A$ that is strictly larg www.acmicpc.net Tag : combinatorics, number theory 문..
[BOJ 16182] Dumae https://www.acmicpc.net/problem/16182 16182번: Dumae The first line contains two space-separated integers $N, M$. ($1 \leq N \leq 300,000,\ 0 \leq M \leq 1,000,000$) In the next $N$ lines, two space-separated integers $L_i,\ R_i$ are given. ($1 \leq L_i \leq R_i \leq N$) In the next $M$ lines, two space-sepa www.acmicpc.net Tag : Topological Sort, Greedy, Path Compression 문제 요약 위상정렬 순서에 어긋나지 않게 자..
[BOJ 17469] 트리의 색깔과 쿼리 https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리 N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의 www.acmicpc.net Tag : Offline Query, DSU, Small To Large 풀이 간선을 제거하는 것은 일단 생각하지 말자. 어떠한 정점 \(A\)에서 갈 수 있는 점은 같은 컴포넌트에 있는 모든 정점이다. 컴포넌트들에 대해 서로 다른 색의 개수를 구하려면 일단 컴포넌트마다 \(std::set\)을 가지고 있어야할 듯하다. 이 때 컴포넌트는 \(DSU\)로 처리하면 되니 2번쿼리를 \(..
[BOJ 2261] 가장 가까운 두 점 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net Tag : Sweeping 풀이 \(N^2\)개의 점 중에 가장 가까운 두 점을 구해야하는 문제인데 \(\binom{N}{2}\)의 경우를 모두 따져보기엔 \(N\)이 굉장히 크다. 적어도 \(O(N\sqrt{N})\), 되도록 \(O(NlogN)\)까지 만들면 좋을 듯하다. 일단 \(N\)개의 점을 \(X\)기준으로 정렬해보자. 정렬한 후 모든 점을 순회하며 \(..
[BOJ 2682] 최대 사이클 1 https://www.acmicpc.net/problem/2682 2682번: 최대 사이클 1 P는 1부터 n까지 수로 이루어진 순열이다. 최대 사이클 1은 P(1), P(P(1)), P(P(P(1))), ... 중 최댓값이다. 예를 들어 수열 P가 (3, 2, 5, 4, 1, 7, 8, 6) 이라면 P(1) = 3 P(P(1)) = P(3) = 5 P(P(P(1))) = P(5) = 1 따라서 3, 5, www.acmicpc.net Tag : Combinatorics 풀이 순열 \(P\)는 \( 1 N >> K; ll ans = 0; for(ll sz = 2; sz
[Boj 1947] 선물 전달 http://icpc.me/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 교란순열이다 dp[i] = (i-1) * (dp[i-1] + dp[i-2]) #include using namespace std; using ll = long long; const int MOD = 1e9; int n; ll dp[1000000 + 5]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; dp[2] = 1; for (int i = 3; i

티스토리툴바