PS 이야기

문제에서 주어진 방법대로, 분수 $\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번 이상하는 것은 비..