알고리즘 문제풀이 썸네일형 리스트형 SCPC 2017 본선 2번 풀이. Bridge 문제 설명(요약)평면 위에 볼록다각형 모양의 두 섬 A와 B가 있다. A와 B는 서로 교차하지 않는다. A와 B 사이에 다리를 놓으려고 하는데, 다리 건설 비용을 최소화하기 위해 다리의 길이를 최소화하려고 한다.다리의 A쪽 끝점 P와 B쪽 끝점 Q에 대해, P는 A의 내부나 경계에, Q는 B나 내부의 경계에 위치해야 한다.다리(선분 PQ)의 길이를 최소화하는 점 P와 Q에 대해, 그 길이를 구하여라.제약 조건: A, B의 꼭짓점 수 N, M은 각각 200,000 이하* 부분문제 1 (82점): N, M 더보기 SCPC 2016 본선 4번 풀이. 반물질 문제 설명www.codeground.org 참조 제약 조건: 1 더보기 SCPC 2016 본선 3번 풀이. 폭격 문제 설명2차원 격자칸 형태의 적국에 폭격을 하려고 한다.격자칸의 가로 크기는 N, 세로 크기는 M 이다.좌표는 가장 왼쪽 위 칸을 (1 , 1)로, 가장 오른쪽 아래 칸을 (M,N)으로 표현한다.각 격자칸에 최대 하나의 목표물이 있으며, 전체 목표물의 개수는 P 로 주어진다.각 폭격기는 3X3크기의 영역에 있는 목표물을 모두 파괴할 수 있으며, 그 영역에 두 개 이상의 목표물이 있어야 출격이 가능하다고 한다.적국의 목표물 위치가 주어졌을 때 모든 목표물을 파괴할 수 있는 최소의 폭격기 수를 계산하라.두 개 이상의 폭격기가 하나의 목표를 파괴하는 것도 가능하다.아래 그림에서 왼쪽의 경우는 어떤 경우에도 한 폭격기는 하나의 목표만 파괴할 수 있어서 폭격이 불가능하다.오른쪽의 경우는 두 대의 폭격기가 출동하.. 더보기 SCPC 2016 2차예선 5번 풀이. 난민촌 문제 설명(요약)평면 위에 N개의 점 (xi, yi)가 있고, N개의 자연수 ai가 주어져 있다. 가상의 평균점 C(xc, yc)와 ai들의 순열 ap(1), ..., ap(N)을 잘 정해 다음 식을 최소화하면 그 최솟값은 얼마인가? 제약 조건: N 더보기 SCPC 2017 1차예선 5번 풀이. Covernent 문제 설명(요약)2N개가 리프 노드를 포함하여 M(>2N)개의 정점을 갖는 트리 T=(V, E)가 있다. 각 엣지에는 양의 가중치가 부여되어 있다. 이 트리의 리프 노드는 1, 2, ..., 2N까지 번호가 붙어 있고, 노드 2N+1, ..., M은 엣지가 2개 이상 연결된 내부 노드이다. 리프 노드 i와 N+i 중 많아야 하나만 선택할 수 있다고 할 때, 이 조건을 만족하는 어떤 부분집합 X에 대해, 이들을 포함하는 최소 연결그래프(서브트리)를 생각할 수 있다. 이 서브트리의 모든 엣지의 가중치의 합을 S(X)라고 하자. 가능한 모든 X를 고려할 때 S(X)의 최댓값을 구하여라.제약 조건: 2 더보기 이전 1 2 3 다음
