www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경�� www.acmicpc.net 이번에도 파라메트릭 서치 문제다. 이번엔 반복문의 시작을 음반에서 가장 큰 값으로 해줘야 하는데, 우리가 찾으려는 값이 무엇인지 알아야 한다. 문제를 잘 읽어보면 우리는 결국 블루레이의 크기를 찾아야 되는데 여기에 이분 탐색이 사용된다. #include #include using namespace std; using ll = long long; int ar[100001], n, m, sum; int main() {..

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색에 대해 공부하는 중이다. 간단한 문제지만 L, R 정하거나 ans값을 찾는 것이 한 번에 되지 않아서 연습해볼 만하다. 정부는 지방마다 각 예산을 할당해야 되는데 예산이 정해져 있어서 우선순위를 둬야 한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정한다. 상..

www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 머리가 아파오는 수학 문제다. 이 문제는 해답을 참고해서 풀었다. 기본적으로 페르마의 소정리를 이용 확장 유클리드 호제법을 이용 이외에 소인수 분해로 푸는 방법이 있는 것 같은데, 나는 페르마의 소정리를 이용해서 풀었다. 페르마의 소정리는 소수 p와 정수 a에 대해 다음을 만족한다. $$a^{(p-1)}\equiv1\;(mod\;p)$$ 따라서 $$nCk = \frac{k!}{(n-k)!}$$ 에서 n! = A, k!(n-k)! = ..

www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제의 내용은 간단하다. 처음에는 map이나 set을 사용해서 각각의 탐색은 O(log N)이니 찾을 수 있을 것 같았지만 #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m, x; vector ar; map M; c..

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 단계별로 풀기에서 힙을 공부하고 응용 겸 풀어본 문제이다. 처음에는 이거 벡터로 해야되는거 아닌가? 싶을 정도로 접근이 안돼서 다른 사람의 풀이를 참고했다. 최대 힙과 최소 힙을 조건에 맞게 나눠서 그때 그때 최대 힙의 top을 출력해주면 된다. 최대힙의 크기는 최소 힙의 크기와 같거나 1만큼만 커야 한다. 최대힙의 top은 최소 힙의 top보다 작아야 한다. 이 두 조건을 만족시키며 구현하면 ..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 �� www.acmicpc.net 이 문제도 1967번과 똑같은 문제다. 다만 입력받는 방식이 조금 귀찮아졌다. 마찬가지로 1번 노드에서 DFS를 돌리고 최댓값의 인덱스를 저장해 두었다가 다시 DFS를 돌리면 된다. #include #include #include using namespace std; bool vis[100001]; vector ar[100001]; int ans, idx; void dfs(int cur, int..