hibye1217 hibye1217

난이도: 539 태그 더보기 Depth First Search (깊이 우선 탐색) 풀이 1. \( N \)번째 동작을 배우기 위해 배워야 하는 동작들은? 더보기 \( N \)번째 동작을 배우기 위해서는, \( A_{N, 1}, A_{N, 2}, \ldots, A_{N, K_N} \)번째 동작을 배워야 합니다. 그런데, 이러한 동작들을 배우기 위해서는 \( A_{A_{N, 1}, 1}, A_{A_{N, 1}, 2}, \ldots, A_{A_{N, 1}, K_{A_{N, 1}}} \)번째 동작 등등을 배워야 합니다. 여기서, 동작들을 정점으로, 동작 간의 선후관계를 간선으로 나타내는 그래프를 만들어봅시다. 즉, \( i \rightarrow A_{i, k} \)를 다 만들어봅시다. 그럼, \( N \)번째 ..

난이도: 90 // 보정 없이는 -197 태그 더보기 Greedy (그리디) 풀이 1. 해독제가 담긴 쿠키는 최대 몇 개를 먹을 수 있을까? 더보기 해독제는 몇 개를 먹어도 상관없으므로, 항상 \( A+B \)개를 먹을 수 있습니다. 2. 독이 담긴 쿠키는 최대 몇 개를 먹을 수 있을까? 더보기 독이 담긴 쿠키는 2번 연속으로 먹으면 안 됩니다. 중간에 해독제가 반드시 1번 들어가야 하죠. 그럼, 독 → 해독 → 독 → 해독 → ... → 독 의 순서로 먹어야 하고, 해독제가 \( X \)개 있었다면 독이 담긴 쿠키는 \( X+1 \)개까지 먹을 수 있습니다. 물론 주어진 개수인 \( C \)개보다 더 많이 먹을 수는 없지만요. 코드 더보기 위 두 과정을 합치면, 해독제가 있는 맛있는 쿠키는 \( B \..

난이도: 69 // 보정 없이는 -417 태그 더보기 Brute Force (브루트 포스) Mathematics (수학) Arithmetic (사칙연산) 풀이 1. \( b \)의 값으로 가능한 수들은? 더보기 \( b > \log_2 N \)이라면, \( 2^b > 2^{\log_2 N} = N \)이 됩니다. 즉, \( b \)의 값으로 가능한 경우는 \( O(\log N) \)가지가 되겠네요. 그러니 가능한 모든 \( b \)에 대해 답을 구해봅시다. 2. \( b \)가 고정되면, \( a, c \)로 써야 하는 값은? 더보기 \( b \)가 고정이 되면, 자연스럽게 \( 2^b \) 역시 고정이 됩니다. 그럼 저희는, \( N = a \times 2^b + c \)이면서 \( a + c \)를 ..

체감 난이도: Diamond IV + 0.37 태그 더보기 Case Work (많은 조건 분기) Ad Hoc (애드 혹) 풀이 1. 1번의 대전 (1 vs 1)에서 얻을 수 있는 정보는? 더보기 \( a \)와 \( b \)가 (이 순서대로) 대결을 했다면, \( a \)가 이김: \( a \)의 패가 \( b \)의 패를 이기거나 비김 \( b \)가 이김: \( b \)의 패가 \( a \)의 패를 이김 이라는 정보를 얻을 수 있습니다. 지금부터는, 편의상 아래와 같은 Notation을 놓겠습니다. \( a^+, a^0, a^- \): 각각 \( a \)를 이기는 패, \( a \)과 비기는 패, \( a \)한테 지는 패 를 의미합니다. \( a \ge b, a < b \): \( a, b \) 순..

체감 난이도: Platinum IV - 0.3 태그 더보기 Binary Search (이진 탐색) & Parametric Search (매개 변수 탐색) Dynamic Programming (동적 계획법) Sliding Window (슬라이딩 윈도우) Set / Multiset 풀이 1. 최대 \( r \)미터를 이동하기 위한 티켓의 가격을 재정비해보자. 더보기 \( r \)미터를 이동하기 위한 티켓의 가격은 이미 문제에서 \( p_r \)로 주어집니다. 하지만, 만약 \( r' > r \)이면서 \( p_r' < p_r \)인 \( r' \)이 존재한다면? 즉, 범위는 더 넓은데 가격이 더 싼 게 존재한다면? \( r \)미터까지만 이동한다 하더라도 \( r' \)에 대한 티켓을 사는 것이 가격 상 이..

체감 난이도: Platinum IV + 0.2 태그 더보기 Sparse Table (희소 배열) Lowest Common Ancestor (최소 공통 조상) 풀이 1. \( E = 0 \)이면? 더보기 잘 알려진 문제입니다. \( d[v] = \) \( 1 \)번 정점부터 \( v \)번 정점까지의 길이, \( l = \text{lca}(v, w) \)라고 할 때 \( \text{dis}(v, w) = \text{dis}(v, l) + \text{dis}(l, w) = d[v]-d[l] + d[w]-d[l] \)입니다. 그러니, \( d[v] \)를 전처리한 후 LCA를 빠르게 구하기 위한 희소 배열까지 만들어주면 됩니다. 2. 추가된 간선을 반드시 타야 한다면? 더보기 추가된 간선이 \( v_1 \)번..

체감 난이도: Gold V + 2.6 태그 더보기 Imperfect Time Complexity (시간복잡도 상으로 느린 풀이가 통과됨) Tree Set 풀이 1. 특정 상자가 놓이는 위치는? 더보기 지금 놓아야 할 상자의 위치가 \( [x_1, x_2] \times [y_1, y_2] \)라고 합시다. 그럼, 이전에 놓인 상자들 중 위 직사각형과 겹치는 상자들만 볼 때, 이 중 가장 높은 곳에 놓인 상자 위에 놓이게 됩니다. 2. 이거 시간 복잡도 괜찮나? 더보기 새로운 상자를 볼 때마다, 이전 상자들을 하나씩 다 둘러보는 방식을 생각해봅시다. 대충 생각해봐도 \( O(N^2) \)입니다. 심지어 \( O(N^2) \)인 데이터도 간단히 만들 수 있습니다. 하지만 \( N \le 20\,000 \)이고..

체감 난이도: Silver I + 0.1 태그 더보기 Geometry (기하) Pythagoras Theorem (피타고라스의 정리) 풀이 1. 원은 굉장히 대칭적인데, 이를 사용해서 작업을 편하게 할 수 있을까? 더보기 \( x \)축과 \( y \)축 대칭을 사용해, 우측 상단의 1/4 부분만 고려해주면 됩니다. 마침 길이가 짝수라고 하니, 1/4로 잘 나눠짐을 볼 수 있습니다. 잘 고민해보면 \( y = x \) 직선까지 고려해서 1/8 대칭을 만들 수는 있지만, 오히려 작업이 귀찮아지므로 위의 1/4만 고려하도록 합시다. 2. 타일을 다루기 쉬운 걸로 바꿔보자. 더보기 타일이라고 하니까, 뭔가 \( (r, c) \)라는 하나의 좌표를 주고 싶게 생겼습니다. 하지만, 타일 하나에 좌표 하나를 주게 ..