hibye1217 hibye1217

난이도: 11 // -1022 태그 더보기 Arithmetic 풀이 1. 간단한 생각 더보기 간선이 14개밖에 없으니까, 그냥 14개의 pair를 저장하고 풀어도 됩니다. 하지만, 이대로는 재미없으니 뭔가 재밌는 풀이를 들고 와봅시다. 2. 재밌는 생각 더보기 \( x \)와 아래로 연결된 두 수를 잘 보면, 각각 \( 2x \)와 \( 2x+1 \)입니다. \( \left\lfloor \frac{2x}{2} \right\rfloor = \left\lfloor \frac{2x+1}{2} \right\rfloor = x \)이므로, \( a = \left\lfloor \frac{b}{2} \right\rfloor \)인지 판별하는 것만으로도 모든 경우를 다 확인해볼 수 있습니다. 3. 코드 더보기 1234..

난이도: Bronze V 태그 더보기 Mathematics 풀이 1. 설명 더보기 N!은, 그 정의상 1부터 N까지의 정수를 곱한 값이 됩니다. 그러니, N을 입력받아 1부터 N까지 곱해서 출력해주면 됩니다. \( 20! = 2\,432\,902\,008\,176\,640\,000 > n; ll res = 1; for (int i = 1; i

난이도: Bronze V // Standard 태그 더보기 Arithmetic 풀이 1. 간단한 설명 더보기 출력 문단만 봐도 알겠지만, 두 정수를 입력받은 뒤 두 수의 차의 절댓값을 출력하면 됩니다. 유일한 주의점은, 입력되는 수는 최대 20억 (int 범위)이지만 두 수의 차이는 최대 40억 (int 범위 바깥)이기 때문에 int를 사용하면 안 됩니다. 2. 코드 더보기 1 2 3 4 void Main(){ ll a, b; cin >> a >> b; cout

난이도: Platinum II 태그 더보기 Offline Query Sweeping Segment Tree Value Compression 풀이 1. \( l \)이 고정되어있다면, 쿼리를 어떻게 처리할까? 더보기 \( l \)번째 항부터 오른쪽으로 한 칸씩 가면서, 새로운 수가 나온다면 1을, 아니면 0을 적어봅시다. 그럼, \( [l, r] \) 쿼리의 답은 \( [l, r] \) 구간에 적힌 1의 개수 = \( [l, r] \) 구간의 합 이 됩니다. 만약 모든 쿼리의 \( l \)이 동일하다면, 위 과정을 전처리한 뒤 \( O(\log N) \)으로 구간합을 처리해주면 되겠죠. 2. 왼쪽 끝점이 \( l \)에서 \( l+1 \)로 이동한다면, 쿼리를 어떻게 처리할까? 더보기 \( l \)에서 \..

난이도: Platinum IV 태그 더보기 Segment Tree Binary Search (on Segment Tree) 풀이 1. 특정 구간 안에서 Bid할 수 있는 물건이 존재하는지 판별해보자. 더보기 돈을 \( x \)만큼 가지고 있는 사람이 Bid할 수 있는 물건은, 현재 가격이 \( x \)보다 저렴한 물건들입니다. 그럼, \( i \)번째 물건의 현재 가격이 \( A_{i} \)라고 하면, \( [s, e] \) 구간에서 Bid할 수 있는 물건이 존재하는지 보려면, \( \min\limits_{s \le i \le e} A_{i} \)이 \( x \)보다 작은지 판별하면 됩니다. min 쿼리는 세그먼트 트리로 잘 처리해주면 되죠. 2. 이를 토대로, 어떤 사람이 Bid하는 위치를 찾아보자. ..

난이도: Gold II 태그 더보기 Implementation Parsing 풀이 1. 구현 디테일 더보기 문제를 풀기 위해서 해야 할 스텝은 다음과 같습니다. 입력받기 → '&'를 기준으로 나누기 → 각각의 문자열을 Alignment에 맞게 적절히 출력 + 중간중간에 표 테두리 출력 그런데 Alignment에 어떻게 잘 맞출까요? 그 Column에 있는 문자열들 중, 가장 긴 문자열의 길이를 l이라고 해봅시다. 저희가 지금 출력해야 하는 문자열은 s고, Alignment 방향은 d라고 합시다. 그럼, d가 ''라면 왼쪽에 잘 달아주면 되겠죠. '='이라면, 양쪽에 적당히 달아주면 됩니다. 표 테두리 출력하는 건, 별찍기 느낌으로 잘 돌려주면 됩니다. '@'를 하나 출력한 뒤, '-'를 (Column의 ..

난이도: Diamond V 태그 더보기 Sparse Table → Range Maximum Query in O(1) Divide and Conquer Precomputation 풀이 1. 한 변의 길이가 \( K \)인 정사각형의 Range Maximum Query는 어떻게 처리할까? 더보기 사실 어느 정도 웰노운이긴 합니다. \( 2^k \le K \)인 최대 \( k \)를 찾은 뒤, 아래와 같이 쿼리를 날리면 됩니다. 2. 한 변의 길이가 \( K \)인 이등변삼각형의 Range Maximum Query를, [1]의 아이디어로 처리할 수 있을까? 더보기 네. 가능합니다. \( 2^k \le K \)인 최대 \( k \)를 찾은 뒤, 아래와 같이 쿼리를 날리면 됩니다. 대신에, 이 경우는 정사각형의 ..

난이도: Platinum II 태그 더보기 Stack → Parenthesis Matching Dynamic Programming (on Tree) → Kth Smallest Element (Ordered) Set Backtracking 풀이 1. 괄호 문자열을 토대로 트리를 만들어보자. 더보기 각각의 괄호 쌍에 대해, 이 안에 있는 다른 괄호 쌍이나 숫자를 이어줍시다. 그러니까... 대강 이런 식으로요. 하나의 괄호 쌍은, 자식으로 다른 괄호 쌍이나 어떤 수를 가지게 됩니다. 그럼, 특정 괄호 쌍을 나타내는 정점에서 만들 수 있는 문자열은, 각 자식에서 만들 수 있는 문자열을 들고 온 뒤, 그 순서대로 concat하는 것으로 볼 수 있겠죠. 또한, 이렇게 트리를 만들면, ()를 뒤집는 건 그 서브트리 ..