PS 이야기

문제 링크 A. Pegman $N \times M$ 크기의 직사각형 모양에서 임의의 위치에서 시작해서 움직인다. 본인이 서 있는 위치에 화살표가 있으면 그 방향으로 다음 화살표를 만날 때까지 걸어가고, 만약 서 있는 위치에 화살표가 없으면 움직이지 않는다. 이 때, 놓여있는 화살표의 방향을 최소한으로 바꿔서 어떤 위치에서 시작하는지와 상관 없이 직사각형 밖으로 넘어가지 않게하는 문제다. 아주 당연히, 화살표가 있는 위치들에 대해서만 고려해주면 된다. 화살표가 있는 위치에 대해서 화살표가 가르키면 안되는 방향들을 바로 구할 수 있다. 그 방향에만 놓지 않도록 최소 개수로 화살표를 바꾸면 된다. #include using namespace std; int yy[]={-1, 0, 1, 0}, xx[]={0, ..

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