hibye1217 hibye1217

난이도: 178 번역 더보기 Holidog는 굉장히 똑똑한 개입니다. 얼마나 똑똑하냐면, 덧셈과 소수 판별을 할 수 있습니다! Holidog에게 어떠한 양의 정수를 주고 이 수가 소수인지 묻는다면, 소수라면 WANWAN이라고 짖고, 아니라면 BOWWOW라고 짖습니다. 당신은, 이 Holidog에게 \( 1 + 2 + 3 + \ldots + N \)이 소수인지 묻기로 했습니다. 이 때 Holidog가 어떻게 짖을 지 출력하세요. 소수란, \( 2 \) 이상의 양의 정수 중 \( 1 \)과 자기 자신을 제외한 다른 양의 정수로 나누어지지 않는 수를 의미합니다. 예로, \( 2 \), \( 3 \), \( 17 \)은 소수이지만, \( 1 \), \( 10 \)은 소수입니다. 태그 더보기 Mathematics..

난이도: 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) \)의 수평 선분에 구멍이 뚫렸다고 해봅시다..

난이도: 1393 태그 더보기 Recursion Divide and Conquer 풀이 1. 어떤 수 \( N \)에 있는 1의 개수를 세보자. 더보기 \( N \)에 있는 1의 개수는, \( N \)을 계속 10으로 나누면서 1의 자리가 1인지 계속 봐주면 됩니다. 2. [1]을 조금 다르게 생각해보자. 더보기 [1]에서 구하는 과정을 잘 생각해보면, (10 이상의 자리에 있는 1의 개수) + (1의 자리에 있는 1의 개수)로 표현할 수 있습니다. 3a. \( 0 \) 이상 \( N \) 이하의 모든 정수에 있는 1의 개수를 세는 방법 더보기 \( f(n) \)를 \( 0 \) 이상 \( n \) 이하의 모든 정수에 있는 1의 개수라고 정의하고 \( g(n) \)을 \( n \)에 있는 1의 개수라고 ..

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