hibye1217 hibye1217

난이도: 1400 태그 더보기 Recursion (재귀) String (문자열) 풀이 1. 쿼리로 들어온 \( k \)가 \( 1 \le k \le n \)이라면? 더보기 자명하게, 입력받은 문자열의 \( k \)번째 문자, 즉 \( S_k \)가 정답이 됩니다. 2. 쿼리로 들어온 \( k \)가, \( x \)번째 쿼리에서 추가된 글자라면? 더보기 \( x \)번째 쿼리를 아래와 같이 나타내봅시다. \( s_1, e_1, s_2, e_2 \): \( S \)의 \( [s_1, e_1] \)번째 글자를 \( [s_2, e_2] \)에 붙여넣는다. (이 때, \( s_2 = |S| + 1, e_2 = |S| + (e_1-s_1+1) \)이 됩니다.) \( k \)번째 글자가 \( x \)번째 쿼리에서 추..

난이도: 800 태그 더보기 Constructive (구성적) Ad-Hoc (애드 혹) 풀이 + 코드 더보기 \( N = 1 \)이라면, \( [1] \)이 가능합니다. \( N = 2 \)라면, \( [1, 1] \) 같은 게 가능합니다. ... \( [1, 1, \ldots, 1] \)을 출력하면, 무슨 부분수열을 잡아도 합 = 길이 이므로, 문제의 답으로써 가능하다는 결론이 나옵니다. 1 2 3 4 5 6 void Main(){ int t; cin >> t; while (t--){ int n; cin >> n; for (int i = 1; i

난이도: 2323 태그 더보기 Probability Theory (확률론) Dynamic Programming (동적 계획법) DP Optimization - Matrix Exponentiation (행렬 거듭제곱으로 DP 최적화하기) Modular Multiplicative Inverse (모듈러 곱셈에 대한 역원) 풀이 1. \( N \)번째 클릭이 발생하는 시각은? 더보기 확률에 의존하기 때문에 당연히 "이 때다!"라고 답할 수는 없습니다. 하지만, 이 생각 자체는 도움이 많이 될 예정이니 따로 적었습니다. 문제의 답은, \( N \)번째 클릭이 발생하는 시간이 T의 방문 시각인지 / A의 방문 시각인지 로 계산할 수 있습니다. 2. \( 1 \)번째 클릭이 \( i \)시에 발생할 확률은? 더보기..

난이도: 1840 태그 더보기 Offline Query (오프라인 쿼리) 쿼리 자체의 순서를 바꾸지는 않지만, 쿼리를 모두 받은 뒤 처리하기 때문에 넣었다. 그와는 별개로, 개인적으로 이 문제에서 \( Q \)보다 \( N \)이 훨씬 쿼리 같다고 느끼기도 했고. Binary Search (이진 탐색) Disjoint-Set Union Skipping the checked cells using DSU (DSU로 이미 사용한 칸 건너뛰기) 요약하자면, 인접한 사용된 칸들을 DSU로 묶어서, 한 번에 점프뛰는 그런 느낌이다. / 동방 프로젝트 (Large)를 생각해보자. 풀이 1. 공사에 대해 생각해보기 더보기 \( [S, T) \) 시간에 위치 \( X \)에서 일어나는 공사는, 어떤 출발시각 \( D \..

난이도: 1739 태그 더보기 Combinatorics (조합론) \( _{n}C_{r} \mod p \) \( (n, r \le p) \) in \( O(N) \) Precomputation & \( O(1) \) Query 풀이 1. 색깔을 칠하는 방식에 대해 더보기 문제에서 말한대로, 각 층에는 4가지 중 하나의 색깔을 칠할 수 있습니다. 하지만 4가지 색깔은 생각하기 어려우니까, \( A \)점의 색깔과 \( B \)점의 색깔 2가지만 고려해봅시다. \( A+B \)점은 두 색깔을 동시에 사용하는 경우로, \( 0 \)점은 아무 색깔도 사용하지 않는 경우입니다. 이렇게 보면 색 \( A \)와 색 \( B \)는 독립적입니다. 풀어서 말하자면, 어떤 층에 \( A \)를 칠했는지와는 관계없이 \(..

난이도: 1696 // 실험적 태그 더보기 Longest Increasing Subsequence Imperfect Time Complexity (당시 정해는 \( O(N \log N) \)으로 추정) 번역 더보기 \( N \)개의 카드가 주어집니다. 각각의 카드에는 정수 하나가 쓰여있습니다. 나열된 카드에 아래 작업을 원하는 만큼 적용시킬 수 있습니다. 원하는 카드 한 장을 빼낸 뒤, 원하는 위치에 삽입한다. 카드에 적힌 수가 오름차순이 되도록 하기 위해 실행해야 하는 작업의 최소 횟수를 구하세요. 추가 조건 두 장 이상의 카드에 같은 수가 적혀있는 경우는 없습니다. 또한, 카드에 적힌 수는 \( 1 \) 이상 \( N \) 이하입니다. 즉, 카드에 적힌 숫자들을 나열하면, 순열이 완성됩니다. 풀이 1..

난이도: 1423 태그 더보기 0-1 BFS 풀이 1. 최단 경로 문제 같으니, 그래프를 구축해보자. 더보기 정점은 \( (r, c) \)로 잡고, 간선은 이동 가능 여부로 잡아주면 기본적인 격자 그래프를 만들 수 있습니다. 하지만, 이대로는 벽을 부수는 게 적용되지 않는데... 2. 최단 경로에서, 우리가 목표로 하는 것은? 더보기 당연하겠지만, 최단 경로 문제에서 목표로 하는 건 한 점에서 다른 점으로 가는 최단 경로를 찾는 것입니다. 이 문제에서는, 벽을 부수는 횟수를 최소화해야 하므로, 벽을 부수는가 여부로 간선에 가중치를 넣어볼 수 있겠네요. 하지만 \( 2 \times 2 \) 칸의 벽을 부숴야 하는데, 정확히 어떻게 해야 할까요? 3. \( (r, c) \)에서 벽을 부술 때 / 부수지 않을..

난이도: 894 // 실험적 번역 더보기 \( N \)개의 정수가 주어집니다. \( i \)번째 수는 \( a_{i} \)입니다. \( l \le r \)이면서 \( a_{l}, a_{l+1}, \ldots, a_{r} \)이 증가수열이 되도록 하는 \( (l, r) \)의 개수를 찾으세요. 즉, \( l \le i < r \)인 모든 \( i \)에 대해 \( a_{i} < a_{i+1} \)를 만족시키는 \( (l, r) \)의 개수를 찾으세요. 태그 더보기 Sweeping (스위핑) 풀이 1. \( l \)을 고정시킬 때, 가능한 개수는? 더보기 조건의 특성상, \( r_1 < r_2 \)이고 \( (l, r_2) \)가 증가수열이었다면, \( (l, r_1) \)도 증가수열이 됩니다. 또한, \(..