hibye1217 hibye1217

난이도: Gold III ± 0.0 (σ = 0.0) 체감 난이도: Gold II - 0.2 태그 더보기 Backtracking (백트래킹) Sieve of Eratosthenes (에라토스테네스의 체) Unknown Time Complexity (시간복잡도가 :blobthinking:) 풀이 1. 나올 수 있는 합의 최댓값은? 이를 토대로, 소수 판정을 해보자면? 더보기 (수열의 길이) × (연속된 합의 길이), 즉 \( (M-N) \times D \)가 됩니다. 문제 제한 상으로는, 약 10000이 되겠네요. 이걸 알고 있으니, 10000까지의 수에 대해 에라토스테네스의 체를 돌려두면 소수 판정의 시간복잡도는 더 이상 신경쓰지 않아도 됩니다. 2. 이걸로, 가능한 경우를 돌려보자면? 더보기 백트래킹을..

난이도: 8 // -1144 태그 더보기 Arithmetic (사칙연산) Mathematics (수학) 풀이 1. 팔로우할 수 있는 최대 유저 수는? 더보기 \( A \)명이 나를 팔로우하고 있으므로, 문제에서 주어진 식에 따라 \( 2A + 100 \)명을 팔로우할 수 있습니다. 2. 그럼, 몇 명을 더 팔로우할 수 있을까? 더보기 현재 \( B \)명을 팔로우하고 있으므로, 남은 자리는 \( 2A + 100 - B \)명이 되겠네요. 코드 더보기 1 2 3 4 5 void Main(){ int a, b; cin >> a >> b; int x = 2*a+100; cout

난이도: 7 // -1208 태그 더보기 Arithmetic (사칙연산) 풀이 더보기 \( a \)를 입력받아서, 문제에 주어진 식을 계산해 출력하면 됩니다. 1 2 3 4 void Main(){ int a; cin >> a; cout

난이도: Gold IV 체감 난이도: Silver I + 0.2 태그 더보기 Parametric Search (매개변수 탐색) Binary Search (이진 탐색) Probability Theory (확률론) 풀이 1. 특정 사람과 달리기를 했을 때, Erik이 이길 확률은? 더보기 어떤 사람이 \( [s, e] \) 시간에 도착하고, Erik은 \( t \)초에 도착한다고 해봅시다. 그럼, 아래와 같은 세 경우에 따라 결정됩니다. \( t < s \): 항상 Erik이 이깁니다. 확률로 따지면 \( 1 \)이 되죠. \( s \le t \le e \): Erik이 이길 확률은 \( \frac{e-t}{e-s} \)가 됩니다, 말로 풀어서 쓰면 (어떤 사람이 Erik보다 느리게 도착할 확률) / (전체..

난이도: Silver IV 체감 난이도: Silver IV + 0.3 태그 더보기 Binary Search (이진 탐색) std::lower_bound, std::upper_bound, std::equal_range Sort (정렬) 풀이 1. 쿼리를 처리하기 전... 더보기 정렬이 되어있는 게 아무래도 데이터 처리에 편할 것으로 추정됩니다. 그러니 데이터를 정렬하고 시작해봅시다. 지금부터는 정렬된 데이터, 즉 \( 1 \le A_1 \le A_2 \le \cdots \le A_N \)을 가정합니다. 2. 1번 쿼리를 처리해보자. 더보기 특정 수 \( k \)보다 크거나 같은 값이 나오는 첫 위치를 \( i \)번째 위치라고 해봅시다. 즉, \( A_1 \le \cdots \le A_{i-1} < k \..

난이도: Bronze V 체감 난이도: Bronze V 태그 더보기 Conditional Statement (조건문) 풀이 1. 점심 식사를 판별하는 방법은? 더보기 입력 제한에 쓰여있듯이, \( 12 \le T \le 16 \)이라면 점심 시간을 의미합니다. 2. 술을 마시는 걸 판별하는 방법은? 더보기 \( S = 1 \)이면 마시는 것이고, 아니면 마시지 않는 것입니다. 코드 더보기 밥알의 개수가 320개가 되려면, 점심 시간이면서 술을 마시지 않아야 합니다. 즉, \( 12 \le T \le 16 \)이면서 \( S = 0 \)이어야 합니다. 1 2 3 4 5 void Main(){ int t, s; cin >> t >> s; if (12

난이도: Bronze V // 표준 체감 난이도: Bronze V 태그 더보기 Arithmetic (사칙연산) 풀이 더보기 두 수 A와 B를 입력받은 뒤, 합 A+B를 계산해 출력하면 됩니다. 1 2 3 4 void Main(){ int a, b; cin >> a >> b; cout

난이도: 1600 태그 더보기 Constructive (구성적) Greedy (그리디) 풀이 1. 수 하나를 추가해서 mex의 결과값을 바꾸는 방법은? 더보기 \( \text{mex}(b_1, b_2, \ldots, b_{i-1}) = a_{i-1} \)에서 \( \text{mex}(b_1, b_2, \ldots, b_{i-1}, b_i) = a_i \)로 값이 바뀌려면 (즉, \( a_{i-1} \neq a_{i} \)라면), \( b_i = a_{i-1} \)여야 합니다. 물론 값이 바뀐다고 정확히 \( a_i \)가 된다는 보장은 없지만, \( b_i = a_{i-1} \)가 아니었다면 애초에 \( a_{i-1} = a_{i} \)가 되어버리기 때문에 위 경우로 고정시킬 수 있습니다. 2. 남은 칸..