PS 이야기

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); } }