레야몬

1. 문제 이 모듈은 사건 내에서 가능한 글자가 하나뿐이면 그 글자를 자동으로 입력한다. 모듈이 단어의 첫 글자를 추론하지 않는다. 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력하여야 한다. 사건이 주어졌을 때, 이 모듈을 사용하면서 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하시오. 여러 개의 테스트 케이스로 주어져 있다. - 1 - 단어의 개수 \(N(1 \leq N \leq 10^{5})\) - N개의 줄 - 1~80글자인 영어 소문자로만 이루어진 단어. 똑같은 단어가 2번 이상 주어지지 않는다. 각 테스트 케이스마다 주어진 단어의 길이의 총합은 최대 \(10^{6}\)이다. 각 테케마다 문제의 정답을 소수점 둘째 자리까지 반올림하여 ..

1. 문제 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명이다. 또한 모든 사람은 모든 일을 할 능력이 있다. 사람과 일은 1~N까지 번호가 매겨져 있다. 모든 일을 하는데 필요한 비용의 최솟값을 구하자. - 1 - 사람과 일의 수 \(N(1 \leq N \leq 20)\) - N개의 줄 - 비용 \(D(1 \leq D \leq 10,000)\) 모든 일을 하는데 필요한 비용의 최솟값 2. 재정의 X 3. 해결 방법 비트필드를 이용한 DP 기본 문제 4. 실수한 점, 개선 방법 얘는 비트필드를 이용할 때 DP에서 탐색하는 no와 상관없이 dp가 같기 때문에 통일해도 된다. 이렇게 푼 다른 사람 코드가 있어서 아래에 링크해두었다. #include us..

1. 문제 두 원이 주어졌을 때, 교차하는 영역의 넓이를 소수점 셋째 자리까지 구하시오. - 1 - 두 원의 중심과 반지름 \(x_{1}, y_{1}, r_{1}, x_{2}, y_{2}, r_{2}\) 실수는 최대 소수점 둘째자리까지 구한다 - 1 - 교차하는 영역의 넓이를 반올림해 소수점 셋째 자리까지 출력한다. 2. 재정의 X 3. 해결 방법 두 점 사이의 거리 \(d = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}}\) 코사인 제2법칙 \(x^{2} + y^{2} - 2xycos(\theta) = z^{2}\) 사인 법칙 \(S = \frac{1}{2} absin(\theta)\) 4. 실수한 점, 개선한 점 X #include #include using ..

1. 문제 N개의 선분들이 2차원 평면상에 주어져 있다. 두 선분이 서로 만나는 경우에 두 선분은 같은 그룹에 속했다고 하며 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 이 N개의 선분들은 몇 개의 그룹으로 되어있을까? 또, 가장 큰 그룹에 속하는 선분의 개수는 몇 개인가? - 1 - \(N(1 \leq N \leq 3,000)\) - N개의 줄 - 선분의 양 끝점의 좌표 \(\left|x_{i} \right|, \left|y_{i} \right| \leq 5,000\) - 1 - 그룹의 수 - 2 - 가장 크기가 큰 그룹에 속한 선분의 개수 2. 재정의 선분 그룹 개수와 그 크기 구하기 3. 해결 방법 N*N = 9,000,000으로 CCW를 이용해 선분 교차를 모두 파악하고 이를 union..

1. 문제 2차원 좌표 평면 위 두 선분 \(L_{1}, L_{2}\)가 주어졌을 때 두 선분의 교차 여부를 판단하자. 한 선분의 각 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. - 1 - \(x_{1}, y_{1}, x_{2}, y_{2}\) - 2 - \(x_{3}, y_{3}, x_{4}, y_{4}\) \((-1,000,000 \leq x_{i}, y_{i} \leq 1,000,000), (x_{i}, y_{i} \in \mathbb{Z}), (0 < l_{1}, l_{2})\) - 1 - 교차하면 1, 아니면 0을 출력 - 2 - 교차하는 점의 x좌표와 y좌표 출력 2. 재정의 교차점 구하기 3. 해결 방법 CCW로 적절히 하면 되는데 너무 조건 분기가 많아서 생략하고 아래 링크..

1. 문제 그래프에서 정점의 부분 집합 S에 속한 모든 정점쌍이 인접하지 않으면 S를 독립 집합이라고 한다. 트리와 각 정점의 가중치가 양의 정수로 주어졌을 때, 최대 독립 집합을 구하시오. - 1 - 트리의 정점수 \(n(1 \leq n \leq 10,000)\) - 2 - n개의 정수, 정점 i의 가중치 \(w_{i}(1 \leq w{i} \leq 10,000, 1 \leq i \leq n)\) - 3 ~ 마지막 줄 - 정점의 쌍으로 간선이 주어짐 - 1 - 최대 독립집합의 크기 - 2 - 최대 독립집합에 속하는 정점을 오름차순으로 출력 최대 독립집합이 여러 개인 경우 하나만 출력하면 된다. 2. 재정의 트리에서 최대 독립 집합 구하기 3. 해결 방법 dp[no][0] += max(dp[next][0..

1. 문제 N개의 마을로 이루어진 나라가 있다. 마을에는 1~N까지의 번호가 붙어있다. 이 나라는 트리 구조이며 무방향성이다. N개의 마을 중 몇 개의 마을을 '우수 마을'로 설정하려고 한다. '우수 마을'로 선정된 마을 주민 수의 총합을 최대로 한다. '우수 마을'끼리는 서로 인접할 수가 없다. ;우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과 인접하여야 한다. - 1 - \(N(1 \leq N \leq 10,000)\) - 2 - 마을 주민 수 \(popu(0 \leq popu \leq 10,000)\) - M-1개줄 - 인접한 두 마을의 번호 '우수 마을'의 주민 수 총합 2. 재정의 트리에서 최대, 인접 X, 반드시 우수가 아닌 마을은 우수와 인접. 이때 최댓값은? 3. 해결 방..

1. 문제 도현이는 n개의 별들을 이어서 별자리를 만들 것이다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태 모든 별들은 별자리 위의 선을 통해 직/간접적으로 이어져야 한다. 별들은 2차원 평면 위에 있고 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 들 때, 별자리를 만드는 최소 비용을 구하시오. - 1 - 별의 개수 \(n(1 \leq n \leq 100)\) - n개의 줄 - 각 별의 x, y좌표(실수) 최대 소수점 둘째 자리까지 \((0 \leq x, y \leq 1,000)\) 정답 출력(절대 상태 오차는 \(10^{-2}\)까지 허용 2. 재정의 좌표간 거리가 비용인 그래프의 최소 스패닝 트리 구하기 3. 해결 방법 \(n^2 = 10,000\)이므로 간선의 가중치가..