hibye1217 hibye1217

난이도: Silver IV 태그 더보기 Mathematics Greedy 풀이 1. 3 kg는 몇 개를 쓸 수 있을까? 더보기 3 kg를 5개 이상 썼다고 해봅시다. 그럼, 동일한 무게를 5 kg 3개로 만들 수 있겠죠. 이는, 3 kg를 최대 4개까지밖에 쓸 수 없음을 의미합니다. 2. 그럼, 문제의 답은? 더보기 3 kg의 봉지를 0개부터 4개까지로 돌리면서, 이에 맞는 5 kg의 개수가 존재하는지 보면 됩니다. 봉지의 개수를 최소화하려면 3 kg의 개수를 최소화해야 하니, 0부터 돌리면서 답이 나오는 순간 종료하면 되겠죠. // 사실 0개부터 4개까지 중에서, 답이 될 수 있는 건 하나밖에 없습니다. // 3x mod 5가 x = 0, 1, 2, 3, 4에 대해 모두 다르기 때문입니다. 3. 코드 ..

난이도: Platinum II 태그 더보기 Topological Sort Maximum Distance in Directed Acyclic Graph 풀이 1. 간선을 자르지 않을 때, 참가자들이 타게 될 최장경로들은? 더보기 DAG이기 때문에, 위상정렬 + 거리 계산을 사용해서 최장경로를 계산할 수 있습니다. 실제 최단경로에 포함되는 간선들은 '가장 멀리 있는 정점'에 도달할 수 있는 정점들 사이의 간선이 되겠죠. // 물론 그 간선이 유의미하게 사용되어야 합니다. 즉, dis[v]+1 = dis[w]여야 하죠. 2. 자를 때 답에 유의미한 영향을 끼치는 간선들은? 더보기 만약, 어떤 간선을 잘랐는데 하나 이상의 최장경로가 유지되었다고 해봅시다. 그럼, 그 최장경로 때문에 답에 변화가 없을 것입니다. ..

난이도: 1739 태그 더보기 Double Counting Combinatorics Prefix/Suffix Query 풀이 1. '?'를 제외하고 생각해보자. 더보기 문자열에 '?'가 없다고 가정해봅시다. 그럼, 문제의 답은 그냥 만들 수 있는 "ABC"의 개수가 됩니다. 이 개수는 어떻게 찾을까요? 중심에 있는 'B'를 하나로 고정해봅시다. 그럼, 그 문자를 사용해서 만들 수 있는 "ABC"의 개수는 왼쪽에 있는 'A'의 개수 × 오른쪽에 있는 'C'의 개수가 됩니다. 문제의 답은 이를 모든 'B'에 대해 고려해주면 됩니다. // 중심에 있는 'B'가 다르기 때문에, 한 문자열을 두번 셀 걱정은 하지 않아도 됩니다. 2. 어떤 문자 'B'를 고정시킬 때, '?'를 포함해서 계산하는 방법은? 더보기 이..

난이도: Platinum III 태그 더보기 Inversion Counting (Line Intersection Counting) Euler Characteristic (증명에 사용됩니다) 풀이 1. 만약 선이 교차하지 않는다면, 나눠지는 조각의 개수는? 더보기 선이 교차하지 않는다면, 위상수학적으로 볼 때 그냥 격자 모양이 됩니다. 즉, \( (N+1)(M+1) \)조각으로 나눠지겠죠. 2. [1]의 상태에서, 선을 하나 교차시켜보면? 더보기 한 쌍의 선이 교차되었고, 조건에 따라 이는 최대 1번 발생합니다. 그럼, 이 교차점이 속하지 않는 면은 무시하고, 교차점이 속하는 면만 봅시다. 위 그림과 같이, 3개였던 면이 4개로 변하는 걸 볼 수 있습니다. 추가로, [1]의 상태에서 교차시킨다고 하지만, ..

난이도: Gold III 태그 더보기 Minimum Spanning Tree Disjoint-Set Union 풀이 1. 모든 컴퓨터가 연결되어있는 상태를 만들 수 있을까? 더보기 만약 초기 상태부터 연결되지 않은 쌍이 존재했다면, 간선을 더 없애도 그 쌍을 연결시킬 수는 없으므로 불가능합니다. 반대로, 모든 컴퓨터가 연결되어있었다면, 간선을 0개 자르는 방식으로 모든 컴퓨터를 연결시킨 상태를 만들 수 있기 때문에, 가능합니다. 2. 기부할 수 있는 랜선의 최댓값은? 더보기 모든 컴퓨터를 연결시키면서 기부할 수 있는 랜선을 최대화한다는 건, 연결성을 유지시키되 남기는 랜선을 최소화한다는 것을 의미합니다. 이는 결국 Minimum Spanning Tree 문제이기 때문에, (총 랜선 길이) - (MST에 ..

난이도: 2125 태그 더보기 Combinatorics Addition Rule Probability Theory Dynamic Programming using Probability Modular Multiplicative Inverse 풀이 1. 앞에 있는 \( N \)개만 두고 볼 때, \( K \)번 추첨해서 \( M \)개를 뽑을 확률은? 더보기 \( dp_{n, m, k} \) = 앞에 있는 \( n \)개만 두고 볼 때, \( k \)번 추첨해서 \( m \)개를 뽑을 확률로 정의해봅시다. 그리고, 이에 맞게 초항부터 설정해봅시다. \( n k \)인 경우: 추첨 횟수보다 더 많이 뽑았다는데, 불가능..

난이도: 1824 // Experimental 번역 더보기 C. 1억 번이 넘는 계산 Takahashi는 \( N^2 \)회의 많은 계산이라는 방식으로 본인의 계산 능력을 늘리려 합니다. \( N^2 \)회의 많은 계산은 아래와 같이 진행됩니다. 우선, \( N \times N \) 크기의 행렬을 준비합니다. 그리고, 행렬의 맨 왼쪽 줄의 왼쪽에는 \( A_{i} \)를 차례로 적고, 맨 윗줄의 위에는 \( B_{j} \)를 차례대로 적습니다. 이제, \( (i, j) \)의 위치에 있는 칸에는 \( A_{i} \times B_{j} \)를 적습니다. Takahashi는 이를 너무 간단하게 끝냈기 때문에, 이렇게 적은 \( N^2 \)개의 수를 정렬해보기로 했습니다. 이 때, 정렬 후 앞에서부터 \( K..

난이도: 128 // -55 태그 더보기 Arithmetic 풀이 1. 무엇을 하면 될까? 더보기 문제에서 나온 대로, 입력받은 수에서 출발해서 함수를 계속 씌우다가, 어느 순간 본 적 있는 수가 나오면 그 때의 인덱스를 출력하면 됩니다. 물론 길어질 때를 대비해서, chk[x] = x가 나온 적이 있는가? 를 사용하는 것이 좋겠죠. 여담으로, 범위 내에서는 항상 ?, 1, 4, 2, 1, ...으로 반복되고, 이게 첫 반복이기 때문에 1의 위치 + 3을 해도 정답이 됩니다. 2. 조금 더 깊은 생각 더보기 '근데 이거 너무 커지지 않을까?' 하는 걱정이 생길 수도 있습니다. 다행히도, 문제 조건에서 1000000을 넘지 않는다고 친절히 제한을 걸었기 때문에 걱정 없이 구현하면 됩니다. 3. 코드 더보기..