티스토리

hibye1217

검색하기

블로그 홈

hibye1217

hibye1217.tistory.com/m

hibye1217 님의 블로그입니다.

구독자: 7

방명록 방문하기

주요 글 목록

[AtCoder - ARC032A] ホリドッグ 난이도: 178 번역 더보기 Holidog는 굉장히 똑똑한 개입니다. 얼마나 똑똑하냐면, 덧셈과 소수 판별을 할 수 있습니다! Holidog에게 어떠한 양의 정수를 주고 이 수가 소수인지 묻는다면, 소수라면 WANWAN이라고 짖고, 아니라면 BOWWOW라고 짖습니다. 당신은, 이 Holidog에게 \( 1 + 2 + 3 + \ldots + N \)이 소수인지 묻기로 했습니다. 이 때 Holidog가 어떻게 짖을 지 출력하세요. 소수란, \( 2 \) 이상의 양의 정수 중 \( 1 \)과 자기 자신을 제외한 다른 양의 정수로 나누어지지 않는 수를 의미합니다. 예로, \( 2 \), \( 3 \), \( 17 \)은 소수이지만, \( 1 \), \( 10 \)은 소수입니다. 태그 더보기 Mathematics.. 공감수 0 댓글수 1 2024. 1. 10.
[Baekjoon - 25682] 체스판 다시 칠하기 2 난이도: 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} \)라면 그 칸을 새.. 공감수 0 댓글수 1 2024. 1. 10.
[Baekjoon - 21605] 아름다운 수열 난이도: 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 \)점이 되는 것을 볼 수 있습니다. // 엄밀한 증명은 수학적 귀납법을 사용합니다... 공감수 0 댓글수 0 2023. 6. 20.
[Baekjoon - 8982] 수족관 1 난이도: Gold III 태그 더보기 Implementation Sweeping? 풀이 1. 선분보다 더 간단한 표현법이 없을까? 더보기 수족관은, 위에서 내려다볼 때 바닥이 모두 보이는 형태입니다. 즉, 하나의 \( x \)좌표는 최대 하나의 수평선분이 차지하고 있다는 의미입니다. // 엄밀히는, 수평선분을 \( [x_1, x_2) \)의 반열린 구간으로 정의할 때입니다. 앞으로도 이 문제에서는 수평선분을 반열린구간으로 정의하겠습니다. 그러니, \( H_x \) = 좌표가 \( x \)인 위치의 깊이 로 수족관의 바닥 상태를 더 간단하게 저장할 수 있습니다. 2. 각각의 구멍은, 특정 위치에 있는 물을 얼마나 빼낼 수 있을까? 더보기 \( [x_1, x_2) \)의 수평 선분에 구멍이 뚫렸다고 해봅시다.. 공감수 0 댓글수 0 2023. 6. 18.
[AtCoder - ABC029 D] 1 난이도: 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의 개수라고 .. 공감수 0 댓글수 0 2023. 6. 6.
[Baekjoon - 17502] 클레어와 팰린드롬 난이도: 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. 코드 더보기 공감수 0 댓글수 0 2023. 6. 5.
[Baekjoon - 16894] 약수 게임 난이도: 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.. 공감수 0 댓글수 0 2023. 6. 3.
[Baekjoon - 10037] Decorating the Pastures 난이도: 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]; .. 공감수 0 댓글수 0 2023. 4. 17.
[Baekjoon - 3411] Jewel heist 난이도: 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 \)를 천천히 늘려나가봅.. 공감수 0 댓글수 0 2023. 3. 14.
[Baekjoon - 19813] Dates 난이도: 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('... 공감수 0 댓글수 0 2023. 3. 13.
[Baekjoon - 18694] Game of Nim Everywhere 난이도: Platinum I 태그 더보기 NIM Game Bitmask Divide and Conquer 풀이 1. 1번 플레이어가 패배할 조건은? 더보기 님 게임에서 패배하는 경우는, 모든 Heap의 xor 합이 0일 때입니다. 지금 문제에서는 Heap이 N, 2N, 3N이므로, \( N \oplus 2N \oplus 3N = 0 \)인 경우겠죠. 그런데, \( 3N = N + 2N = (N \& 2N) \ll 1 + N \oplus 2N \)입니다. \( N \oplus 2N \oplus ((N \& 2N) \ll 1 + N \oplus 2N) = 0 \)을 만족하려면, \( N \& 2N = 0 \)이어야 합니다. 이는 \( N \)과 \( 2N \)에 동시에 켜진 비트가 없어야 한다는 것을 의미하.. 공감수 0 댓글수 0 2023. 3. 9.
[AtCoder - ABC195 E] Lucky 7 Battle 난이도: 1609 태그 더보기 Game Theory Dynamic Programming (with Game Theory) Modular Arithmetic 풀이 1. 게임의 시작, 중간, 끝 과정을 어떻게 나타낼 수 있을까? 더보기 어차피 종료 시점에서 필요한 건 7의 배수 여부입니다. 그러므로, 중간 과정은 현재까지 계산된 수 mod 7을 가지고 있으면 되겠죠. 물론 몇 턴을 진행했는가 역시 과정에 저장하고 있어야 합니다. 그러므로, 실제 상태는 "\( (i, x) \) = \( i \)번의 턴을 진행했고, 현재 쓰인 값 mod 7은 \( x \)"로 나타낼 수 있습니다. 2. [1]에서 정의한 상태를 두고 볼 때, 그 상태에서 누가 승리하는지 알아내보자. 더보기 \( dp_{i, x} \) = 상태 .. 공감수 0 댓글수 0 2023. 3. 9.
[CodeForces - 1062C] Banh-mi 난이도: 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이 됩니.. 공감수 0 댓글수 0 2023. 3. 9.
[Baekjoon - 10763] Bessie's Birthday Buffet 난이도: Gold I 태그 더보기 Dynamic Programming Breadth-First Search 풀이 1. 특정 Patch에서 멈추면서, 에너지를 최대로 하려면? 더보기 \( dp_{v} \) = \( v \)번 Patch에서 멈추면서, 받을 수 있는 최대 에너지 를 생각해봅시다. 저희는 Patch의 Quality가 증가하는 순서대로 이동할 것이므로, 점화식을 아래와 같이 써볼 수 있습니다. \( dp_{v} = \max\limits_{Q_w < Q_v}(0, dp_{w} - E \cdot d_{v, w}) + Q_v \) // 여기서 \( d_{v, w} \)는 \( v \)와 \( w \) 사이의 거리를 의미합니다. \( N \) 제한이 작으니, \( O(N^2) \)에 DP를 구해줄 수 .. 공감수 0 댓글수 0 2023. 3. 9.
[AtCoder - AGC034 B] ABC 난이도: 1101 태그 더보기 Stack 풀이 1. 연산을 분석해보자. 더보기 문제에서 주어진 연산은 "ABC"를 "BCA"로 바꾸는 연산입니다. 이를 다르게 해석하자면, "A" 다음에 "BC"가 온다면 이 "A"를 "BC" 뒤로 미는 연산이라고 볼 수 있겠죠. 즉, "A"가 "BC"를 건너뛰어서 이동한다는 것입니다. 이 연산을 최대한 많이 하려면, "A"가 최대한 많은 "BC"를 건너뛰어야겠죠. 2. 이를 토대로, 간단히 생각해볼 수 있는 풀이는? 더보기 글자를 하나씩 읽으면서, 'A'가 나올 때마다 이 뒤에 연속적으로 있는 BC의 개수를 세주면 되죠. 다만, 주의할 점이 AAABCBC라든가, AABCABC라든가, AABCBAC라든가 다양합니다. // A 뒤에 A가 나와도 이동 가능, 심지어 BC 사이.. 공감수 0 댓글수 0 2023. 3. 9.
[AtCoder - ARC121 A] 2nd Greatest Distance 난이도: 459 태그 더보기 Mathematics Sorting 풀이 1. 1차원에서 생각해보자. 더보기 문제가 1차원이었다면 어떻게 풀었을까요? 가장 멀리 있는 두 점은 자명히 min과 max가 됩니다. 2번째로 가장 멀리 있는 두 점은 min이 한 칸 이동하거나 max가 한 칸 이동한 경우 중 더 먼 거리가 됩니다. 그러므로, 실질적으로 값을 비교할 때는 1, 2, N-1, N번째 값에 대해서만 비교해주면 됩니다. // 물론 여기서 i번째 값은 정렬된 후의 i번째를 의미합니다! 2. [1]의 생각을 2차원으로 확장해보자. 더보기 x축의 차이와 y축의 차이 중 더 큰 값을 가지고 온다는데, 그럼 이렇게 생각해볼 수 있습니다. [1]의 생각을 그냥 x축에 대해서 계산하고 y축에 대해서 계산한다면? x축을.. 공감수 0 댓글수 0 2023. 3. 9.
[Baekjoon - 26099] 설탕 배달 2 난이도: 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. 코드 .. 공감수 0 댓글수 0 2023. 3. 9.
[Baekjoon - 18199] Commemorative Race 난이도: Platinum II 태그 더보기 Topological Sort Maximum Distance in Directed Acyclic Graph 풀이 1. 간선을 자르지 않을 때, 참가자들이 타게 될 최장경로들은? 더보기 DAG이기 때문에, 위상정렬 + 거리 계산을 사용해서 최장경로를 계산할 수 있습니다. 실제 최단경로에 포함되는 간선들은 '가장 멀리 있는 정점'에 도달할 수 있는 정점들 사이의 간선이 되겠죠. // 물론 그 간선이 유의미하게 사용되어야 합니다. 즉, dis[v]+1 = dis[w]여야 하죠. 2. 자를 때 답에 유의미한 영향을 끼치는 간선들은? 더보기 만약, 어떤 간선을 잘랐는데 하나 이상의 최장경로가 유지되었다고 해봅시다. 그럼, 그 최장경로 때문에 답에 변화가 없을 것입니다. .. 공감수 0 댓글수 0 2023. 3. 8.
[AtCoder - ABC104 D] We Love ABC 난이도: 1739 태그 더보기 Double Counting Combinatorics Prefix/Suffix Query 풀이 1. '?'를 제외하고 생각해보자. 더보기 문자열에 '?'가 없다고 가정해봅시다. 그럼, 문제의 답은 그냥 만들 수 있는 "ABC"의 개수가 됩니다. 이 개수는 어떻게 찾을까요? 중심에 있는 'B'를 하나로 고정해봅시다. 그럼, 그 문자를 사용해서 만들 수 있는 "ABC"의 개수는 왼쪽에 있는 'A'의 개수 × 오른쪽에 있는 'C'의 개수가 됩니다. 문제의 답은 이를 모든 'B'에 대해 고려해주면 됩니다. // 중심에 있는 'B'가 다르기 때문에, 한 문자열을 두번 셀 걱정은 하지 않아도 됩니다. 2. 어떤 문자 'B'를 고정시킬 때, '?'를 포함해서 계산하는 방법은? 더보기 이.. 공감수 0 댓글수 0 2023. 3. 8.
[Baekjoon - 16444] Contador de Pizza 난이도: Platinum III 태그 더보기 Inversion Counting (Line Intersection Counting) Euler Characteristic (증명에 사용됩니다) 풀이 1. 만약 선이 교차하지 않는다면, 나눠지는 조각의 개수는? 더보기 선이 교차하지 않는다면, 위상수학적으로 볼 때 그냥 격자 모양이 됩니다. 즉, \( (N+1)(M+1) \)조각으로 나눠지겠죠. 2. [1]의 상태에서, 선을 하나 교차시켜보면? 더보기 한 쌍의 선이 교차되었고, 조건에 따라 이는 최대 1번 발생합니다. 그럼, 이 교차점이 속하지 않는 면은 무시하고, 교차점이 속하는 면만 봅시다. 위 그림과 같이, 3개였던 면이 4개로 변하는 걸 볼 수 있습니다. 추가로, [1]의 상태에서 교차시킨다고 하지만, .. 공감수 0 댓글수 0 2023. 3. 8.
[Baekjoon - 1414] 불우이웃돕기 난이도: Gold III 태그 더보기 Minimum Spanning Tree Disjoint-Set Union 풀이 1. 모든 컴퓨터가 연결되어있는 상태를 만들 수 있을까? 더보기 만약 초기 상태부터 연결되지 않은 쌍이 존재했다면, 간선을 더 없애도 그 쌍을 연결시킬 수는 없으므로 불가능합니다. 반대로, 모든 컴퓨터가 연결되어있었다면, 간선을 0개 자르는 방식으로 모든 컴퓨터를 연결시킨 상태를 만들 수 있기 때문에, 가능합니다. 2. 기부할 수 있는 랜선의 최댓값은? 더보기 모든 컴퓨터를 연결시키면서 기부할 수 있는 랜선을 최대화한다는 건, 연결성을 유지시키되 남기는 랜선을 최소화한다는 것을 의미합니다. 이는 결국 Minimum Spanning Tree 문제이기 때문에, (총 랜선 길이) - (MST에 .. 공감수 0 댓글수 0 2023. 3. 6.
[AtCoder - ABC243 F] Lottery 난이도: 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 \)인 경우: 추첨 횟수보다 더 많이 뽑았다는데, 불가능.. 공감수 0 댓글수 0 2023. 3. 6.
[AtCoder - ARC037 C] 億マス計算 난이도: 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.. 공감수 0 댓글수 1 2023. 3. 6.
[AtCoder - ABC116 B] Collatz Problem 난이도: 128 // -55 태그 더보기 Arithmetic 풀이 1. 무엇을 하면 될까? 더보기 문제에서 나온 대로, 입력받은 수에서 출발해서 함수를 계속 씌우다가, 어느 순간 본 적 있는 수가 나오면 그 때의 인덱스를 출력하면 됩니다. 물론 길어질 때를 대비해서, chk[x] = x가 나온 적이 있는가? 를 사용하는 것이 좋겠죠. 여담으로, 범위 내에서는 항상 ?, 1, 4, 2, 1, ...으로 반복되고, 이게 첫 반복이기 때문에 1의 위치 + 3을 해도 정답이 됩니다. 2. 조금 더 깊은 생각 더보기 '근데 이거 너무 커지지 않을까?' 하는 걱정이 생길 수도 있습니다. 다행히도, 문제 조건에서 1000000을 넘지 않는다고 친절히 제한을 걸었기 때문에 걱정 없이 구현하면 됩니다. 3. 코드 더보기.. 공감수 0 댓글수 0 2023. 3. 6.
[AtCoder - ABC101 A] Eating Symbols Easy 난이도: 38 // -545 태그 더보기 Arithmetic 풀이 1. 그래서 무엇을 하면 될까? 더보기 문자열 S를 입력받아서, 문제에서 나온 대로 '+'일 때마다 1을 더하고 '-'일 때마다 1을 뺴서 출력하면 됩니다. 2. 코드 더보기 1 2 3 4 5 void Main(){ string s; cin >> s; int ans = 0; for (char c : s){ ans += (c=='+' ? +1 : -1); } cout 공감수 0 댓글수 0 2023. 3. 6.
[Baekjoon - 8314] Acyclic Decomposition 난이도: Platinum V 태그 더보기 Directed Acyclic Graph Topological Sort Depth-First Search 풀이 1. 입력된 그래프가 이미 DAG라면? 더보기 이미 사이클이 없으므로 굳이 더 나눌 필요가 없습니다. 이 때의 답은 1이 됩니다. 2. 입력된 그래프가 DAG가 아니라면? 더보기 항상 2개로 나눌 수 있습니다. 간단한 방법은, 정점 번호를 기준으로 v w인 간선으로 나누는 방법이 있습니다. 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 29 30 31 32 33 34 35 36 37 38 39 40 vector adj[10002.. 공감수 0 댓글수 0 2023. 3. 6.
[Baekjoon - 1920] 수 찾기 난이도: Silver IV 태그 더보기 Binary Search Sort 풀이 1. 수열 \( A \)가 정렬되어있다면, 원하는 수를 어떻게 빠르게 찾을 수 있을까? 더보기 수열 \( A \)가 정렬되어있으니, 이진 탐색을 통해 빠르게 원하는 값의 유무를 판별할 수 있습니다. 2. [1]을 사용해서 문제를 풀 수 있을까? 더보기 원소 간의 의 순서는 상관이 없으니, \( A \)를 정렬해도 아무런 문제가 없습니다. 그러니, 정렬한 뒤 이진 탐색을 해주면 되겠죠. 3. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 int arr[100020]; void Main(){ int n; cin >> n; for (int i = 1; i > arr[i]; } sort(arr+1, arr+n+1); int .. 공감수 0 댓글수 0 2023. 3. 6.
[CodeForces - 1374E2] Reading Books (hard version) 난이도: 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 \)권의 재밌는 .. 공감수 0 댓글수 0 2023. 3. 5.
[CodeForces - 604B] More Cowbell 난이도: 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.. 공감수 0 댓글수 0 2023. 3. 4.
[AtCoder - ABC212 G] Power Pair 난이도: 2150 태그 더보기 Number Theory Primitive Root Prime Factorizations, Divisors Fermat's Little Theorem Modular Multiplicative Inverse Greatest Common Divisor + Highly Composite Number Combinatorics 풀이 1. 소수 모듈러가 가지는 특징을 생각해보자. 더보기 소수 모듈러는 다양한 특징을 가지고 있습니다. 이 중에서 이번에 저희들이 사용할 건 아래와 같습니다. 모든 소수 \( P \)는 적어도 하나 이상의 원시근 \( G \)를 가진다. // 원시근이 뭔지 모르는 사람들을 위해: // 소수 \( P \)의 원시근은 \( G^1, G^2, G^3, \ldots.. 공감수 0 댓글수 0 2023. 3. 4.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.