hibye1217 hibye1217

난이도: 1600 태그 더보기 Greedy Prefix Sum 풀이 1. 하나의 배열에서, 신경써야 하는 건? 더보기 하나의 배열에서 신경써야 하는 건 그 배열 속의 0과 1의 개수 뿐입니다. 2. 무슨 순서대로 처리해야 할까? 더보기 Exchange Argument를 생각해보면, 큰 값부터 사용해야 합니다. // 더 작은 값을 먼저 사용한다면, 그 뒤에도 작은 수가 더해져서 답이 더 작아지기 때문이죠. 3. 이 때의 답은? 더보기 이를 적용시키면, 우선 모든 1을 처리한 뒤 모든 0을 처리해야 함을 알아차릴 수 있습니다. 이제 1이 어떻게 처리되는지 봅시다. 1번째 수는 1이 됩니다. 2번째 수는 1+1 = 2가 됩니다. 3번째 수는 1+1+2 = 4가 됩니다. 4번째 수는 1+1+2+4 = 8이 됩니..

난이도: 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 \)권의 재밌는 ..

난이도: 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..

난이도: 2100 태그 더보기 Greedy Graph Theory Connected Component Disjoint Set Union Priority Queue 풀이 1. 다른 Region에 있는 도시는 몇 번 연결해야 하는가? 더보기 다른 Region에 있는 도시를 하나 연결할 때마다 연결 요소의 개수가 1씩 줄어들게 됩니다. 그러므로, 입력된 그래프의 연결 요소를 \( c \)라고 할 때, \( q-c \)번 연결해야겠죠. 2. 답이 No인 경우는? 더보기 [1]에 따르면, 연결 횟수인 \( p \)는 \( 0 \le p \le q-c \)여야 합니다. 이를 만족하지 못한다면, 답은 No가 되겠죠. No가 나오는 케이스가 하나 더 있는데, \( m = 0, p \neq 0, q = n \)입니다. ..

난이도: 1900 태그 더보기 Dynamic Programming → DP on Tree (트리에서의 동적 계획법) Greedy (그리디) Depth-First Search (깊이 우선 탐색) 풀이 1. 특정 정점에 쓰인 값을 맨 위로 올려보자. 더보기 특정 값을 맨 위로 올리는 대신, 특정 "정점"을 맨 위로 올려보자는 생각입니다. 그 정점에 쓰인 값을 \( 0 \)이라고 하면, 다른 정점에는 \( 0 \)보다 큰 값이나 \( 0 \)보다 작은 값이 들어가게 됩니다. 이를 각각 \( + \)와 \( - \)라고 표현해봅시다. 2. [1]을 토대로, 특정 정점을 맨 위로 올릴 때 우리가 해야 하는 걸 보자. 더보기 대강 이렇게 생각해보면, 0이 맨 위로 올라간다는 소리는 이 과정에서 만나는 max와 mi..

난이도: 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. 남은 칸..

난이도: 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