PS 이야기

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개의 행을 모두 덮는..

비트 문자열이 있을 때, 각 자리의 비트를 switch 할 수 있는 규칙이 2가지 있다. 이 두 가지 규칙을 통하여 주어진 비트 문자열의 모든 자리를 0으로 만드는 최소 회수를 구하는 문제다. 문제를 뒤집어 모든 자리가 0으로 되어 있는 비트 문자열에서 입력으로 주어진 비트 문자열을 만들기 위한 최소 회수를 구하는 문제로 바꾸자. 그러면 이제 왼쪽에 있는 1비트 부터 차례대로 만드는 것이 회수를 최소화 한다. 아래와 같은 값을 미리 계산해둔다. D[i] = 비트문자열의 모든 자리가 0이라고 할 때, 오른쪽에서 i번째 비트를 1로 만드는 최소 회수 D[i] = D[i-1]*2+1, D[1] = 1 D[i] = 2^i - 1 가장 왼쪽에 있는 1비트를 만들기 위한 최소 회수는 몇 일까? 그 비트의 위치를 왼..

자동차가 C대 있고 각 자동차의 시작 위치가 다를 수 있다. 모든 자동차의 목적지는 1번 마을이고, 각 자동차는 최단 경로 중 임의의 한 경로로 이동한다고 하자. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없을 때, 목적지에 갈 수 있는 자동차의 최대 개수를 구하는 문제다. 이 문제는 2013년 월드 파이널 C번 문제와 지문 하나 다르지 않게 출제되었다. 다행히도 이 문제의 풀이를 미리 알고 푼 팀은 없는 것으로 알고 있다. 문제에서 제약 조건은 단 하나, 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없다는 것이다. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동하기 위한 필요충분조건은 두 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 같다는 조건이다. 따라서 자동차..

길이가 N인 문자열이 주어지고, 길이가 M인 패턴이 주어진다. 이 패턴의 연속된 일부분 혹은 전체를 한 번 뒤집어서 새로운 패턴들을 만들 수 있다. 길이가 N인 문자열에서 이렇게 만들어진 패턴들과 매치되는 부분 문자열이 몇 개인지 세어주는 문제다. N ≤ 1,000,000 이고 M ≤ 100 이다. 시간제한은 0.2초로 N에 선형인 시간복잡도를 요구한다. 길이가 M인 패턴에서 뒤집는 연산에 의해 만들어지는 새로운 패턴의 개수는 많아야 $M^2$개다. 즉, 이 문제는 길이가 M인 패턴 $M^2$개와 길이가 N인 문자열을 매칭하는 문제로 바꿀 수 있다. 이와 관련된 문제는 Aho-Corasick 자료구조를 이용하면된다. KMP와 같은 문자열 매칭 알고리즘은 하나의 패턴과 전체 문자열을 매칭하는 알고리즘인데,..

2차원 좌표계에 N 개의 점이 주어졌을 때, 유클리드 거리상 가장 먼 두 점을 찾는 문제이다. 가장 먼 두 점 구하기 글에 풀이가 소개되어 있다. #include using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) typedef long long lld; int T, N; struct Z{ int x, y; } A[MAXN]; int ccw(int ax, int ay, int bx, int by, int cx, int cy) { lld k = (lld)(bx-ax)*(cy-ay)-(lld)(cx-ax)*(by-ay); if (k > 0) return 1; if (k) return -1; r..

문제에서 주어진 방법대로, 분수 $\frac{a}{b} (a < b)$ 를 단위 분수의 합으로 나타냈을 때 마지막 단위 분수의 분모를 구하는 문제다. 문제 입력 형식의 마지막 조건에 따라 $\frac{a}{b}$ 를 구성하는 단위 분수는 31개 미만이다. 이제 문제에서 중요한 것은 $\frac{a}{b} \geq \frac{1}{x}$ 를 만족하는 최소 x 를 구하는 것이다. 이분 검색을 통해서 구해도 되고, 직접 계산을 통해 구해도 된다. 매번 이를 계산하면서 마지막 분수를 구하면 된다. #include typedef long long lld; int T; lld gcd(lld a,lld b){ return b?gcd(b,a%b):a; } struct Z{ Z(lld p,lld q){ lld g = g..

문제에서 $m \times n$ 크기의 토로이드 그래프를 정의한다. 이 토로이드 그래프에서 해밀턴 회로를 찾는 것이 문제다. 문제 조건에서 $m, n \geq 3$ 이므로 모든 $m \times n$ 크기의 토로이드 그래프에서 해밀턴 회로가 존재함을 알 수 있다. i) m이 짝수일 때, ii) m이 홀수일 때, 위와 같이 이동하면 해밀턴 회로가 된다. #include int T, N, M; int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &M); puts("1"); for (i=0;i

주어진 연료 G 안에 도착점에 최단 시간으로 도착하는 방법을 찾는 문제다. 한 칸 이동을 할 때 L 시간 만큼 걸리고, 방향을 회전할 때 마다 시간이 1 만큼 걸린다. 이 문제에서 아래 방향과 오른쪽 방향으로만 움직일 수 있으므로, 각 위치까지 가는 시간은 여태까지 회전한 회수에 따라 결졍 된다. 즉, r행 c열에 있는 칸까지 k번 회전하였다면 걸린 시간은 총 ((r-1)+(c-1))*L + k 이다. 따라서, D[r][c][k][d]=현재 위치는 r행 c열, 회전한 회수는 k, 현재 바라보는 방향은 d 일 때 최소 연료 사용량이라 정의하고 Dynamic Programming 을 하면 된다. 시작점에서 도착점까지 이동할 때 방문하는 지점은 많아야 199개 이며, 각 지점에서 회전을 2번 이상하는 것은 비..

호텔에 온 손님들은 101호 부터 시작하여 201호, 301호, ..., H층 1호에 배정 되며, 그 이후에는 102호, 202호, ..., H층 2호에 배정된다. 시간복잡도 O(HW) 만에 계산을 하여도 되지만, 규칙을 잘 살펴보면 한 번에 N 번째 손님이 배정 받는 방 번호를 알 수 있다. #include int T,H,W,N; int main() { for (scanf("%d",&T);T--;){ scanf("%d%d%d",&H,&W,&N); printf("%d%02d\n",(N-1)%H+1,(N-1)/H+1); } }