문제 풀이/Baekjoon Online Judge
-
[Baekjoon - 18694] Game of Nim Everywhere문제 풀이/Baekjoon Online Judge 2023. 3. 9. 21:58
난이도: 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 \)에 동시에 켜진 비트가 없어야 한다는 것을 의미하..
-
[Baekjoon - 10763] Bessie's Birthday Buffet문제 풀이/Baekjoon Online Judge 2023. 3. 9. 09:49
난이도: 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를 구해줄 수 ..
-
[Baekjoon - 26099] 설탕 배달 2문제 풀이/Baekjoon Online Judge 2023. 3. 9. 08:19
난이도: 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. 코드 ..
-
[Baekjoon - 18199] Commemorative Race문제 풀이/Baekjoon Online Judge 2023. 3. 8. 14:00
난이도: Platinum II 태그 더보기 Topological Sort Maximum Distance in Directed Acyclic Graph 풀이 1. 간선을 자르지 않을 때, 참가자들이 타게 될 최장경로들은? 더보기 DAG이기 때문에, 위상정렬 + 거리 계산을 사용해서 최장경로를 계산할 수 있습니다. 실제 최단경로에 포함되는 간선들은 '가장 멀리 있는 정점'에 도달할 수 있는 정점들 사이의 간선이 되겠죠. // 물론 그 간선이 유의미하게 사용되어야 합니다. 즉, dis[v]+1 = dis[w]여야 하죠. 2. 자를 때 답에 유의미한 영향을 끼치는 간선들은? 더보기 만약, 어떤 간선을 잘랐는데 하나 이상의 최장경로가 유지되었다고 해봅시다. 그럼, 그 최장경로 때문에 답에 변화가 없을 것입니다. ..
-
[Baekjoon - 16444] Contador de Pizza문제 풀이/Baekjoon Online Judge 2023. 3. 8. 09:24
난이도: Platinum III 태그 더보기 Inversion Counting (Line Intersection Counting) Euler Characteristic (증명에 사용됩니다) 풀이 1. 만약 선이 교차하지 않는다면, 나눠지는 조각의 개수는? 더보기 선이 교차하지 않는다면, 위상수학적으로 볼 때 그냥 격자 모양이 됩니다. 즉, \( (N+1)(M+1) \)조각으로 나눠지겠죠. 2. [1]의 상태에서, 선을 하나 교차시켜보면? 더보기 한 쌍의 선이 교차되었고, 조건에 따라 이는 최대 1번 발생합니다. 그럼, 이 교차점이 속하지 않는 면은 무시하고, 교차점이 속하는 면만 봅시다. 위 그림과 같이, 3개였던 면이 4개로 변하는 걸 볼 수 있습니다. 추가로, [1]의 상태에서 교차시킨다고 하지만, ..
-
[Baekjoon - 1414] 불우이웃돕기문제 풀이/Baekjoon Online Judge 2023. 3. 6. 17:32
난이도: Gold III 태그 더보기 Minimum Spanning Tree Disjoint-Set Union 풀이 1. 모든 컴퓨터가 연결되어있는 상태를 만들 수 있을까? 더보기 만약 초기 상태부터 연결되지 않은 쌍이 존재했다면, 간선을 더 없애도 그 쌍을 연결시킬 수는 없으므로 불가능합니다. 반대로, 모든 컴퓨터가 연결되어있었다면, 간선을 0개 자르는 방식으로 모든 컴퓨터를 연결시킨 상태를 만들 수 있기 때문에, 가능합니다. 2. 기부할 수 있는 랜선의 최댓값은? 더보기 모든 컴퓨터를 연결시키면서 기부할 수 있는 랜선을 최대화한다는 건, 연결성을 유지시키되 남기는 랜선을 최소화한다는 것을 의미합니다. 이는 결국 Minimum Spanning Tree 문제이기 때문에, (총 랜선 길이) - (MST에 ..
-
[Baekjoon - 8314] Acyclic Decomposition문제 풀이/Baekjoon Online Judge 2023. 3. 6. 11:33
난이도: 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..
-
[Baekjoon - 1920] 수 찾기문제 풀이/Baekjoon Online Judge 2023. 3. 6. 10:46
난이도: 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 ..