본문 바로가기

BOJ

(56)

[BOJ 20968] Group Photo https://www.acmicpc.net/problem/20986 20986번: Group PhotoAt 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 arewww.acmicpc.netTag : 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번: DumaeThe 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-sepawww.acmicpc.netTag : Topological Sort, Greedy, Path Compression 문제 요약위상정렬 순서에 어긋나지 않게 자리를 배..

[BOJ 17469] 트리의 색깔과 쿼리 https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의www.acmicpc.netTag : Offline Query, DSU, Small To Large 풀이간선을 제거하는 것은 일단 생각하지 말자. 어떠한 정점

A

에서 갈 수 있는 점은 같은 컴포넌트에 있는 모든 정점이다. 컴포넌트들에 대해 서로 다른 색의 개수를 구하려면 일단 컴포넌트마다 std::set을 가지고 있어야할 듯하다.이 때 컴포넌트는 DSU로 처리하면 되니 2번쿼리를 std::set::size를..

[BOJ 2261] 가장 가까운 두 점 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도www.acmicpc.netTag : Sweeping 풀이

N^{2}

개의 점 중에 가장 가까운 두 점을 구해야하는 문제인데

(\binom{N}{2})

의 경우를 모두 따져보기엔

N

이 굉장히 크다. 적어도

O (N \sqrt{N})

O (N l o g N)

까지 만들면 좋을 듯하다. 일단

N

X

기준으로 정렬해보자. 정렬한 후 모든 점을 순회하며 \(std:..

[BOJ 2682] 최대 사이클 1 https://www.acmicpc.net/problem/2682 2682번: 최대 사이클 1P는 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.netTag : Combinatorics 풀이순열

P

1 \(P_{P_{1}}

....를 반복해1로 돌아오는 사이클 안에서 가장 큰 수를 구하는 문제이다. 일단 문제 이름부터 사이클이니 그래프로 해석해봐야 할 듯한 느낌이 강하게 든다. 그러기 위해서 일단 \(1P_..

[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

[boj 1365] 꼬인 전깃줄 icpc.me/1365 1365번: 꼬인 전깃줄첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 ��www.acmicpc.net아이디어는 다음과 같은 조건에서 얻을 수 있다꼬인 전깃줄을 최소로 풀어서 꼬여있는 쌍이 없도록 한다이것이 문제에서 요구하는 것인데 x,y(x>y)에서 각각 a,b로 가는 전깃줄이 있다면b가 a보다 큰 경우에 전깃줄이 있다는 것이 자명하다그렇다면 a[i] = j일때 i에서 j로 전깃줄이 연결되어 있다 생각하면LIS를 구하는 문제가 아닐까?라고 떠올릴 수 있다 코드#include int n;int arr[100000 + 5]; ..

티스토리툴바