PS 이야기

문제 링크 B. Comma Sprinkler 길이가 최대 1,000,000인 문장들이 주어진다. 어떤 단어 앞에 콤마(,)가 오면 같은 단어 앞에 모두 콤마가 오도록 바꾸며, 어떤 단어 뒤에 콤마가 올 경우 같은 단어 뒤에 모두 콤마가 오도록 바꿔야한다. 단, 단어의 끝과 시작에서 부자연스럽게 콤마를 추가하진 않는다. 이 때, 최종 문장을 구하는 문제다. 같은 단어들을 묶어 정점으로 만든다. 그리고 정점을 단어 앞에 콤마가 오는 경우, 단어 뒤에 콤마가 오는 경우를 나타내는 두 정점으로 이원화한다. 단어 앞에 콤마가 오거나, 단어 뒤에 콤마가 오는 경우 해당하는 정점에 색칠은 한 뒤, 원래 문장에서 인접한 두 단어의 정점에는 방향성 간선을 만들어주어 Flood-Fill 한다. 그러면 시간복잡도 $O(V+..

문제 링크 C. Ceiling Function $K$개의 노드로 구성된 Binary Search Tree가 $N$개 주어진다. 이 때 서로 다른 모양을 갖는 BST의 개수를 구하는 문제다. 구조체를 써서 BST를 구현하고 두 노드에 대해 각 노드를 루트로한 서브트리가 같은지 비교해주는 재귀 함수를 구현하여 쉽게 해결할 수 있다. #include using namespace std; int N, M; int A[21]; struct NODE { NODE(int val=0): val(val) { left = right = 0; } int val; NODE *left, *right; } *root[51]; bool identical(NODE *a, NODE *b) { if ((bool)a->left != (b..

문제 링크 A. Amalgamated Artichokes 1부터 N까지 정수 k가 있을 때, price(k) 에 대해 최대 감소폭을 구하는 문제다. 이전까지 나온 최대 값을 저장해두고 현재 값이 최대값 보다 같거나 작다면 최대 감소폭에 차이를 갱신해주고, 현재 값이 최대값 보다 크다면 최대값을 갱신해주면 된다. 시간복잡도는 $O(N)$이다. #include using namespace std; int P, A, B, C, D, N; int main() { double mx = -2e9, ans = 0; scanf("%d%d%d%d%d%d", &P, &A, &B, &C, &D, &N); for (int i=1;i v) ans = max(ans , mx - v); else mx = v; } printf("%..

문제 링크 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]*..