아무 말

https://www.acmicpc.net/problem/1615 1615번: 교차개수세기 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. www.acmicpc.net 들어가며.. 기존에 이 문제의 풀이는 \(O(M \log(N)) \)에 작동하는 세그먼트 트리를 활용하는 것으로 알려져 있었다. 하지만, 이번 포스팅에서는 조금 다른 풀이를 다루고자 한다. 풀이 무려 \(O(NM)\)에 작동하는 코드가 통과된다. 먼저, 간선이 연결된 정점 중, A에 속한 정점을 기준으로 단조 증가하게 정렬한다. (만약 그 정점이 같은 것 들은 B에 속한 정점을 기준으로..

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 들어가며.. 오른쪽은 이 문제의 태그다. 풀고 나서 보니 신기한게 많지만.. 그냥 백트래킹 문제이다. 풀이 우리가 표현해야 하는 공간은 고작 5×5 사이즈이다. 따라서 경우의 수는 고작 \(2^{25} = 33554432\)이므로, 충분히 통과할 수 있다. 그리고 사실 저 만큼의 경우의 수를 탐색하지도 않는다. 탐색을 진행할 때 현재 선택한 칸에서 인접한 칸으로만 방문할 것이며, 임도연 파에 속한 학..

https://www.acmicpc.net/problem/16367 16367번: TV Show Game Your program is to read from standard input. The input starts with a line containing two integers, k and n (3 < k ≤ 5,000, 1 ≤ n ≤ 10,000), where k is the number of lamps and n the number of game participants. Each of the following n lines contains t www.acmicpc.net 관찰 해당 문제에서는 사람들의 추론 결과를 이용하여 모두가 3개 중 2개 이상의 색을 맞출 수 있는지 확인하라고 하고 있다. 이는..

2008년 Google code jam round A에 나왔던 문제이다. 이 문제에서는 매우 정밀한 수의 연산을 요구하기 때문에 double이나 float, Decimal 등을 이용한 연산이 옳은 결과를 내지 못하도록 설계되어 있다. Solution 먼저, \( (3 + \sqrt{5})^{n} \)에 대해서 생각해 보자. \(\sqrt{5}\)가 살짝 거슬린다. 이를 해결하기 위해 \( (3 - \sqrt{5})^{n}\)을 더해준다. 그러면 \(\sqrt{5}\)가 존재하는 모든 항을 없앨 수 있다. 조금 더 자세히 설명하자면, \( (3+\sqrt{5})^{n}+(3-\sqrt{5})^{n}=\sum_{i=0}^{n} (3)^{n-i}(\sqrt{5})^{i}+\sum_{i=0}^{n} (3)^{n..

https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicp..

https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 들어가며.. 이 포스팅에서 사용할 풀이는 해당 문제의 정해가 아닐 수 있다. 풀이 먼저, 트라이(Trie)는 문자열을 저장하고 검색하기 위한 자료구조로, 트라이에 저장된 모든 문자열은 만약 서로의 공통 접두사가 있을 때, 해당하는 노드들을 공유한다. 오른쪽의 그림은 트라이를 나타낸 그림이다. 그림을 보면 바로 이..

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 일단 간단하게 2 개의 수가 있을 때를 생각해보자. Let. \(A,\;B \in \mathcal{N}\), \(A \equiv B \pmod{M} \) \(A \, = A \, - \, \lfloor \frac{A}{M} \rfloor \times M \, + R\) 이므로 (단, \(A \mod \, M \, = \, R\)) \( A \, - \, \lfloor \frac{A}{M} \rfloor \time..

백준의 큰 수 연산 시리즈입니다. 이상하게도 큰 수의 나눗셈이 필요한 문제는 따로 등록되어 있다. 큰 수의 연산을 해야 하는 시리즈인 만큼 함께 다루겠다. 특별히 교육적이거나 한 내용은 아니므로 심심할 때 재미 삼아 풀어보길 바란다. * A+B 시리즈의 문제의 경우, 큰 수의 연산을 하기 위한 노력을 필요로 하는 문제들이 아니었으므로 다루지 않겠다. A/B https://www.acmicpc.net/workbook/view/6546 문제집: A/B (시리즈) www.acmicpc.net 풀이 1008번: A/B 그냥 A/B를 출력한다. 15792번: A/B -2 정수 부분을 구해주고, 소수 부분을 따로 구해준다. 16428번: A/B -3 케이스를 적당히 잘 쪼개면 된다. 문제에 나온 식을 만족하는 값을..

https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M( www.acmicpc.net 풀이를 위한 발상 한 정점을 루트로 하는 트리에서 다른 두 정점의 LCA를 찾아야 한다. 조금 생각을 해보면, 이때의 LCA는 세 정점의 접합점이라는 것을 알 수 있다. 조금 더 구체적으로 표현하자면 다음과 같다. 한 정점으로 트리를 분할했을 때, 정점 r, u, v는 모두 서로 다른 서브 트리에 존재할 수 있게 하는 정점. 이를 토대로 생각하면, 아무 노드나 잡..

21756번: 지우개 풀이 진짜 진짜.. 그냥 시뮬레이션 돌리자. 소스코드 #include using namespace std; int A[103]; int main(){ int N,ans; scanf("%d",&N); for(int i=1;i