PS 이야기

문제 링크 K. Trash Removal 다각형이 주어질 때, 다각형이 쓰레기 장으로 들어가기 위한 통로의 최소 너비를 구하는 문제다. 임의의 두 점을 잡아 직선을 그렸을 때, 그 직선이 수직하게 들어간다고 가정하고 너비를 계산한다. 계산된 너비 중 최소 너비가 답이 된다. 이와 같은 알고리즘이 가능한 이유는 다각형을 덮는 볼록 껍데기를 생각했을 때 너비가 최소가 되는 경우는 볼록 껍데기의 변들 중 한 변이 통로의 변과 평행하기 때문이다. #include #include #include using namespace std; int N; int X[101], Y[101]; double w[101][101]; double dist(int a, int b, int c) { double area2 = X[a]*..

문제 링크 A. Cluster Analysis $N$개의 수가 주어진다. 두 수의 차이가 $K$ 이하면 두 수가 같은 cluster 안에 포함된다. 이 때 생기는 cluster의 개수를 구하는 문제다. $N \leq 100$으로 제한이 굉장히 작다. 따라서 $O(N^2)$ 안에 그래프의 간선을 그릴 수 있고, union-find나 flood-fill을 통하여 cluster의 개수를 세면 된다. #include #include int T, N, K; int A[101], par[101]; int find(int n){ return par[n]==n ? n : (par[n] = find(par[n])); } int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;..

코드포스 GYM 링크 A. Avoiding the Apocalypse 내가 아직 풀지 않았다. B. Button Bashing $n$ 종류의 버튼을 눌러 전자레인지의 시간을 맞추는 문제다. 시간은 음수가 될 수 없고, 1시간보다 많이 지날 수 없기 때문에 0~3600 사이에서 BFS를 돌리면 된다. #include #include using namespace std; int T, N, K; int D[3601], A[17]; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &K); for (i=1;i1, a&1?".5":""); continue; } int ans = 0; for (i=1;i scnt) q -= scnt; for ..

온라인 아카이브 링크 A. The Mountain of Gold? 0번 도시에서 시작하고 시공간을 이동할 수 있는 수단들이 주어졌을 때, 0번 도시의 과거로 돌아올 수 있는지 판별하는 문제다. 일반적으로 $O(NM)$ 시간복잡도의 Bellman-ford 알고리즘은 전체 그래프에서 음수 싸이클이 있는지 판별할 때 쓰인다. 이 문제에서는 0번 도시와 강하게 연결된 연결 요소(0번 도시에서 $x$로 갈 수 있고, $x$에서 0번 도시로 올 수도 있는 $x$들의 집합)에서 음수 싸이클이 있는지 Bellman-ford로 $O(NM)$만에 확인해주면 된다. #include #include #include using namespace std; typedef vector arr; int T, N, M; int D[10..

온라인 아카이브 링크 A. Number Assignment 문제에서 주어진 수들을 정렬한 다음 Dynamic Programming를 이용해 해결한다. D[i][j] = 1~i번 수가 있고, 이를 j개의 그룹으로 나눴을 때 가능한 최소 비용 합 점화시은 아래와 같다. D[i][j] = min(D[k][j-1] + A[i] - A[k+1]) (for j-1 ≤ k < i) 총 시간복잡도는 $O(N^2M)$이다. #include #include using namespace std; int T, N, M; int A[101], D[101][101]; int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); s..

코드포스 GYM 링크 B. Colored Blanket 이 문제에서 입력이 어떻게 들어오든 상관 없이 답은 항상 존재한다. 이 사실을 간략하게 보이겠다. 담요가 $k$개 있고, 색상 종류가 최대 $n$개 일 때 아래와 같은 두 조건을 만족한다. 가장 공이 적은 색상의 공의 개수 ≤ $\frac{k}{n}$가장 공이 많은 색상의 공의 개수 ≥ $\frac{k}{n}$ 위 두 조건을 만족하기 때문에 하나의 키트에 가장 공이 적은 색상의 공들을 모두 넣고 남은 빈 공간을 가장 공이 많은 색상의 공으로 채우면 하나의 키트에는 두 색만 존재하여 문제 조건을 만족한다. 그리고 문제는 귀납적이게 한 단계로 줄어든다. 남은 공의 개수는 $k - \frac{k}{n}$개이며, 색상의 종류는 최대 $n-1$개다. #inc..

2차원 좌표계에 모든 변이 x축과 평행하거나 y축에 평행한 직사각형 하나와 선분 하나가 주어졌을 때 교차점의 개수를 구하는 문제다. 이 문제를 편하게 해결하기 위해 두 선분이 주어졌을 때 생기는 교차점의 개수를 세는 함수 intersect(line a, line b)를 생각하자. 두 선분이 서로 다른 직선 성분일 경우, ccw 함수를 이용하여 두 선분이 교차하는지 확인할 수 있다. 만약 교차하면 생기는 교차점의 개수는 1개이며, 교차하지 않는다면 교차점의 개수는 0이다. ccw(point a, point b, point c): (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) 점 a에서 점 b로 갔다가 점 c로 갔을 때 꺽이는 방향이 시계 방향인지 반시계 방향인지 판별하는 함수(..

$1 \times 1$ 크기의 격자 $MN$ 개가 $M \times N$ 크기의 직사각형을 이루고 있다. 각 격자에는 얼룩이 묻어있을 수 있다. $3 \times 3$ 크기의 덮개를 써서 모든 얼룩을 덮고자 할 때, 필요한 덮개의 최소 개수를 구하는 문제다. 이 문제에서 중요한 것은 $M$ 제한이 $N$ 제한에 비해 현저히 작다는 점이다.한 열에 덮개를 배치하는 경우의 수를 생각해보자. 우선 최악의 경우를 고려하기 위해 $M=10$이라 생각하자. 하나의 덮개를 덮개의 가장 윗 행 번호로 표현하자. 같은 행 번호에 여러 덮개가 있으면 항상 비효율적이며, 9번 행과 10번 행으로 표현되는 덮개는 없다. 따라서 $2^8 = 256$가지를 생각할 수 있다. 좀 더 경우의 수를 줄여보자. 10개의 행을 모두 덮는..

두 개의 요트가 있고, 요트를 이용하고 싶은 사람들의 예약 정보 시작 날짜, 끝 날짜, 대여 비용이 주어졌을 때, 최대 이윤을 구하는 문제다. 이 문제는 weighted interval scheduling의 확장판으로 two room weighted interval scheduling이다. 만약 요트가 두 개가 아니라 한 개라면 $O(N \lg N)$ Dynamic Programming 으로 해결할 수 있다. 이와 관련된 자료는 구글에 검색하여 쉽게 찾을 수 있다. 편의상 입력으로 주어진 예약(proposal)을 구간으로 표현하겠다. 이 문제를 $O(N^2)$ Dynamic Programming으로 해결할 수 있지만, 제한 시간을 초과한다. 이 방법에 대한 설명은 생략한다. 문제 입력 형식에 가장 중요한..

버스를 타는 버스 정기권과 버스와 기차를 모두 타는 전체 정기권이 기간 별로 주어지고, 각 날 마다 버스와 기차 타는 회수가 주어졌을 때, $N$일 동안 버스와 기차를 타는 최소 비용을 구하는 문제다. 문제에서 정기권의 기간과 요금, 그리고 단일 회수로 탑승할 때의 비용은 입력과 상관없이 항상 같게 정해져있다. Dynamic Programming을 생각해볼 수 있다. D[i][j] = i번째 날 까지 버스와 기차를 타고, 현재 남은 버스 정기권의 기간이 j일 때 최소 비용 위와 같이 다이나믹 배열을 정의하자. 이처럼 정의하는 이유가 있다. 전체 정기권을 산 경우 정기권 기간내에는 고려할 사항이 아무 것도 없지만, 버스 정기권을 산 경우 정기권 기간 내에 전체 정기권을 사는게 더 이익일 수 있기 때문이다...