전체 글
-
[AtCoder - ABC101 A] Eating Symbols Easy문제 풀이/AtCoder 2023. 3. 6. 12:18
난이도: 38 // -545 태그 더보기 Arithmetic 풀이 1. 그래서 무엇을 하면 될까? 더보기 문자열 S를 입력받아서, 문제에서 나온 대로 '+'일 때마다 1을 더하고 '-'일 때마다 1을 뺴서 출력하면 됩니다. 2. 코드 더보기 1 2 3 4 5 void Main(){ string s; cin >> s; int ans = 0; for (char c : s){ ans += (c=='+' ? +1 : -1); } cout
-
[Baekjoon - 8314] Acyclic Decomposition문제 풀이/Baekjoon Online Judge 2023. 3. 6. 11:33
난이도: Platinum V 태그 더보기 Directed Acyclic Graph Topological Sort Depth-First Search 풀이 1. 입력된 그래프가 이미 DAG라면? 더보기 이미 사이클이 없으므로 굳이 더 나눌 필요가 없습니다. 이 때의 답은 1이 됩니다. 2. 입력된 그래프가 DAG가 아니라면? 더보기 항상 2개로 나눌 수 있습니다. 간단한 방법은, 정점 번호를 기준으로 v w인 간선으로 나누는 방법이 있습니다. 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 vector adj[10002..
-
[Baekjoon - 1920] 수 찾기문제 풀이/Baekjoon Online Judge 2023. 3. 6. 10:46
난이도: Silver IV 태그 더보기 Binary Search Sort 풀이 1. 수열 \( A \)가 정렬되어있다면, 원하는 수를 어떻게 빠르게 찾을 수 있을까? 더보기 수열 \( A \)가 정렬되어있으니, 이진 탐색을 통해 빠르게 원하는 값의 유무를 판별할 수 있습니다. 2. [1]을 사용해서 문제를 풀 수 있을까? 더보기 원소 간의 의 순서는 상관이 없으니, \( A \)를 정렬해도 아무런 문제가 없습니다. 그러니, 정렬한 뒤 이진 탐색을 해주면 되겠죠. 3. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 int arr[100020]; void Main(){ int n; cin >> n; for (int i = 1; i > arr[i]; } sort(arr+1, arr+n+1); int ..
-
[CodeForces - 1374E2] Reading Books (hard version)문제 풀이/CodeForces 2023. 3. 5. 01:47
난이도: 2500 태그 더보기 Greedy Binary Search on Segment Tree 풀이 1. 누가 좋아하는가에 맞춰서 책을 나눠보자. 더보기 Alice가 좋아하는 책에는 1로, Bob이 좋아하는 책은 2로 분류해봅시다. 만약 둘 다 좋아한다면 1+2 = 3으로 분류하고, 둘 다 싫어한다면 0으로 분류하겠습니다. 2. 만약 1번 분류의 책을 2번 분류의 책보다 더 적게 읽을 거라면, 어떻게 책을 읽을 수 있을까? 더보기 \( C_i \) = \( i \)번 분류의 책을 "최소" 몇 권 읽을 것인지의 조건이라고 해봅시다. 그럼, [2]번 질문은 \( C_1 \le C_2 \)라는 추가 조건을 의미합니다. 여기에, \( C_1 \)을 고정시켜봅시다. Alice는 적어도 \( k \)권의 재밌는 ..
-
[CodeForces - 604B] More Cowbell문제 풀이/CodeForces 2023. 3. 4. 23:45
난이도: 1400 태그 더보기 Binary Search Parametric Search Greedy 풀이 1. 크기 \( s \)를 고정시켜볼까? 더보기 크기 \( s \)를 증가시킬수록, 필요한 상자의 개수는 비증가합니다. // 크기가 늘어나도, 동일한 배치를 유지하면 필요한 상자 수를 그대로 유지할 수 있기 때문이죠. 즉, \( k \)개 이하가 필요한 위치를 파라메트릭 서치 + 이진 탐색으로 찾아볼 수 있습니다. 2. 크기 \( s \)를 고정시켰을 때, 필요한 상자의 개수는? 더보기 남은 물건들 \( s_1, s_2, \ldots, s_N \)을 상자에 담는 방식을 생각해봅시다. 이 때, \( s_N \)이 담기는 상자를 자세히 봅시다. \( s_N \)이 담긴 상자에 남은 공간은 \( s - s..
-
[AtCoder - ABC212 G] Power Pair문제 풀이/AtCoder 2023. 3. 4. 22:26
난이도: 2150 태그 더보기 Number Theory Primitive Root Prime Factorizations, Divisors Fermat's Little Theorem Modular Multiplicative Inverse Greatest Common Divisor + Highly Composite Number Combinatorics 풀이 1. 소수 모듈러가 가지는 특징을 생각해보자. 더보기 소수 모듈러는 다양한 특징을 가지고 있습니다. 이 중에서 이번에 저희들이 사용할 건 아래와 같습니다. 모든 소수 \( P \)는 적어도 하나 이상의 원시근 \( G \)를 가진다. // 원시근이 뭔지 모르는 사람들을 위해: // 소수 \( P \)의 원시근은 \( G^1, G^2, G^3, \ldots..
-
[AtCoder - Panasonic2020 D] String Equivalence문제 풀이/AtCoder 2023. 3. 4. 20:51
난이도: 1102 태그 더보기 Backtracking 풀이 1. Normal Form 문자열이 가지는 특징은? 더보기 앞에서부터 1글자씩 읽어봅시다. 글자를 읽을 때마다, 아래 두 경우 중 하나가 나오게 됩니다. 이미 나온 글자인 경우 앞에서 나온 글자이므로, 앞에서 나왔던 그 글자와 동일해야 합니다. 이는, 여기의 글자를 다른 걸로 바꾼다면 앞의 글자를 건드리게 되기 때문에, 앞의 글자부터 읽는 상황일 때는 딱히 건드릴 수가 없죠. 새로 나온 글자인 경우 지금까지 나오지 않은 글자 중 가장 작은 글자여야 합니다. // 그렇지 않다면, 그 글자로 바꿔서 더 작은 문자열을 만들 수 있기 때문입니다. 즉, 앞에서부터 1글자씩 읽으면서 새로 나오는 글자가 순서대로 a, b, c, d, ...여야 합니다. 반대..
-
[AtCoder - ABC163 D] Sum of Large Numbers문제 풀이/AtCoder 2023. 3. 4. 20:25
난이도: 960 태그 더보기 Mathematics → Combinatorics 풀이 1. \( 10^{100} + m \)의 수들을 더할 때, 무언가 특징이 있지 않을까? 더보기 \( 10^{100} \)은 충분히 큰 수입니다. \( \frac{200\,000 \times 200\,001}{2} \approx 2 \times 10^{10} \)임을 감안하면 더더욱이요. 선택 방식을 약간 바꿔서 \( 0 \)부터 \( N \)까지 중에서 \( A_1, A_2, \ldots, A_K \)를 선택한 뒤 각각의 수에 \( 10^{100} \)을 더하고선 이의 합을 구한다면, \( \sum\limits_{k=1}^{K} 10^{100} + A_k = 10^{100}K + \sum\limits_{k=1}^{k} A..