dh_0e

UCPC 2024 예선 J번 문제로, 대회 도중에 팀원이 풀던 문제를 이어받아 반례를 찾았고, 이를 해결한 뒤 제출했지만 끝내 풀지 못하고 아쉬워하며 대회를 마쳤다.#include #include #include using namespace std;int n;int ans = 0;string coins;vector tPos;int f(int left, int right) { for (int i = left + 1; i > t; while (t--) { tPos.clear(); cin >> n; cin >> coins; ans = 0; int leng = coins.length(); for (int i = 0; i 애드..

2022 UCPC 예선 B번, 그리디로 풀 수 있는 선분 교차 판정 문제로, N  해결 방법 가중치를 기준으로 정렬한 뒤 가중치가 낮은 베기부터 ccw 알고리즘으로 교차되는 선분의 개수를 구하여 가중치에 곱한 값을 모두 더하여 답을 도출했다. [알고리즘] CCW(Counter Clockwise) 알고리즘CCW 알고리즘CCW(Counter Clockwise)는 세 점의 방향 관계를 판별하는 알고리즘이다.주로 기하학적 문제에서 사용되며, 점 A, B, C가 있을 때 이 세 점이 시계 방향으로 배열되어 있는지, 반 시계 방향으dh-0e.tistory.com #include #include #include using namespace std;typedef long long ll;struct Point { ..

CCW 알고리즘CCW(Counter Clockwise)는 세 점의 방향 관계를 판별하는 알고리즘이다.주로 기하학적 문제에서 사용되며, 점 A, B, C가 있을 때 이 세 점이 시계 방향으로 배열되어 있는지, 반 시계 방향으로 배열되어 있는지를 판단한다.이를 통해 다각형의 내부에 점이 있는지, 선분이 교차하는지 등을 판별할 수 있다.원리벡터의 외적(cross product)을 이용하여 세 점의 방향을 결정한다.점 A, B, C의 좌표를 (Ax, Ay), (Bx, By), (Cx, Cy)라 할 때, 다음과 같은 수식을 사용한다.CCW 값 = (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)CCW 값 > 0: 점 A, B, C가 반시계 방향으로 배열되어 있음CCW 값 CCW 값..

2022년 UCPC 예선 J번 문제로, 문제를 처음 읽고 나서 STL sort에 cmp 함수 만들어서 제약을 걸어주면 되는 거 아닌가?라는 생각에 쉽게 풀릴 것 같았지만 제약이 생각대로 걸리지 않았고, 다음과 같은 방법으로 해결했다. 해결 방법 (에드혹) 원래 배열을 정렬이 끝난 배열과 비교하는 과정에서 A(정렬 전 배열의 i번째에 있던 값)와 B(정렬 후 배열의 i번째에 있는 값)가 있다고 가정하자.A = B라면 위치가 변하지 않은 것으로 확인할 게 없이 넘어가면 된다.A ≠ B라면 B의 정렬 전 위치에 있던 수가 C라고 하자. C = A라면 A와 B의 위치가 바뀐 것이므로  A x B가 제곱수인지 확인하면 된다. 하지만 C가 A가 아니라면?A, B, C 모두가 다른 것은 A ↔ B, B ↔ C 이런 ..