hibye1217 hibye1217

난이도: Gold V 태그 더보기 Prefix Sum (Multidimensional) 풀이 0. Notation 더보기 \( A \) : 입력받은 보드. 세로가 \( N \)칸, 가로가 \( M \)칸이다. \( C \): 체스판 무늬를 띄고 있는 보드 (우측 상단의 칸은 Context에 따라 달라질 수 있음) 1. \( K \times K \)로 잘려져 있는 체스판을 칠하는 데 필요한 최소 비용은? 더보기 다르게 말하자면, \( A \)가 이미 \( K \times K \)일 때를 의미합니다. 이 경우, 체스판의 무늬가 어떻게 되었든, \( A_{i, j} = C_{i, j} \)라면 그 칸은 칠하지 않고 놔둘 수 있습니다. 하지만, \( A_{i, j} \neq C_{i, j} \)라면 그 칸을 새..

난이도: Silver I 태그 더보기 Constructive 풀이 1. 얻을 수 있는 최고점은 몇 점일까? 더보기 사용되는 수가 +1과 -1 뿐이고, 수에 -1이 곱해질 수도 있으니 각 \( B_i \)의 최고점과 최저점을 같이 계산해봅시다. \( B_0 \)은 정의상 0점입니다. \( B_1 \)은 \( \pm B_0 \pm 1 = 0 \pm 1 \)이므로, 최소 -1점, 최대 +1점이 됩니다. \( B_2 \)는 \( \pm B_1 \pm 1 = \pm 1 \pm 1 \)이므로, 최소 -2점, 최대 +2점이 됩니다. ... 이런 식으로 규칙을 따르다 보면, \( B_N \)은 최소 \( -N \)점, 최대 \( +N \)점이 되는 것을 볼 수 있습니다. // 엄밀한 증명은 수학적 귀납법을 사용합니다...

난이도: Gold III 태그 더보기 Implementation Sweeping? 풀이 1. 선분보다 더 간단한 표현법이 없을까? 더보기 수족관은, 위에서 내려다볼 때 바닥이 모두 보이는 형태입니다. 즉, 하나의 \( x \)좌표는 최대 하나의 수평선분이 차지하고 있다는 의미입니다. // 엄밀히는, 수평선분을 \( [x_1, x_2) \)의 반열린 구간으로 정의할 때입니다. 앞으로도 이 문제에서는 수평선분을 반열린구간으로 정의하겠습니다. 그러니, \( H_x \) = 좌표가 \( x \)인 위치의 깊이 로 수족관의 바닥 상태를 더 간단하게 저장할 수 있습니다. 2. 각각의 구멍은, 특정 위치에 있는 물을 얼마나 빼낼 수 있을까? 더보기 \( [x_1, x_2) \)의 수평 선분에 구멍이 뚫렸다고 해봅시다..

난이도: Bronze II 태그 더보기 Palindrome 풀이 1. \( s_{i} \)와 관계가 있는 글자는 무엇이 있을까? 더보기 \( s_{i} \)는 앞에서부터 \( i \)번째 글자를 의미합니다. 그럼, 뒤에서부터 \( i \)번째 글자, 즉 \( s_{N+1-i} \)와 동일해야겠죠. 2. 그럼, \( s_{i} \)를 모른다면 관계 있는 글자들로 뭘 할 수 있을까? 더보기 \( s_{i} = s_{N+1-i} \)이므로, 그 글자를 그대로 들고 오면 됩니다. 2a. 만약 그 관계 있는 글자도 모른다면 어떻게 할까? 더보기 다른 글자와는 상관이 없으므로, 두 위치에 똑같은 글자를 아무거나 넣어주면 됩니다. 3. 코드 더보기

난이도: Gold III 태그 더보기 Game Theory Number Theory → Prime Factorization 풀이 1. \( N = 1 \)이라면? 더보기 아무 행동도 할 수 없으니, 정의상 koosaga가 승리합니다. 2-1. 어떤 소수 \( p \)에 대해, \( N = p \)라면? 더보기 \( p \)를 지운 뒤 아무것도 할 수 없으니, koosaga가 승리합니다. 2-2. \( N = p^2 \)이라면? 더보기 koosaga는 \( p^2 \)을 \( p \)로 바꿀 수 밖에 없고, 이후는 [2-1]에 의해 cubelover가 승리합니다. 2-3. \( N = p^3 \)이라면? 더보기 koosaga가 \( p^3 \)을 \( p^2 \)으로 바꾸면, [2-2]에 의해 koosag..

난이도: Gold II 태그 더보기 Bipartite Graph 풀이 1. 주어진 조건을 만족하는 그래프는 어떤 모양일까? 더보기 F를 하나의 색으로, J를 다른 하나의 색으로 보면 영락없는 이분 그래프가 됩니다. 즉, 이분 그래프의 조건을 만족하지 않는다면 답은 자연스럽게 -1이 되겠죠. 2. 그럼, 문제의 답은? 더보기 이분 그래프의 각 컴포넌트를 두 색으로 나누는 방법은 유일합니다. // 엄밀히는, 색1과 색2를 swap하는 경우를 제외하고요. 그러므로, 그렇게 나눈 뒤 둘 중 더 많은 쪽을 J로 정해주면 됩니다. 3. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 vector adj[50020]; ..

난이도: Platinum I 태그 더보기 Sweeping Segment Tree TreeSet Coordinate Compression 풀이 1. 모든 색깔을 가지지 않는 확실한 방법은? 더보기 어떤 하나의 색깔을 고의적으로 피한다면, 적어도 그 색깔을 가지지 않을 것임은 분명하니 모든 색깔을 가지지 않을 수 있습니다. 2. 특정 색깔을 가지지 않겠다고 해보자. 그럼, 가져갈 수 있는 개수의 최댓값은? 더보기 그 색깔을 가지고 있는 점의 위치를 \( (y_1, x_1), (y_2, x_2), \ldots, (y_N, x_N) \)이라고 해봅시다. 또한, \( y_1 \le y_2 \le \ldots y_N \)이라고 해봅시다. 이제 저희가 설치할 Robotic Hand의 \( y \)를 천천히 늘려나가봅..

난이도: Bronze II 태그 더보기 Parsing 풀이 1. '.'으로 나누는 것과 '/'로 나누는 것의 차이는? 더보기 두 방식의 차이는 day와 month의 순서밖에 없습니다. 이는 swap(day, month)만 해줘도 될 정도로 간단하죠. 2. 그렇다면? 더보기 일단 입력받고, '.'나 '/'로 나눠준 뒤, '.'으로 정규화를 시켜봅시다. // 이는 만약 '/'였다면 [1]을 해주면 됩니다. 그 뒤로는 '.'의 결과를 출력하고, [1]을 해준 뒤, '/'의 결과를 출력해주면 됩니다. 3. 코드 더보기 1 2 3 4 5 6 7 for _ in range(int(input())): arr = input() typ = '.' in arr; arr = list( map(int, arr.split('...