PS 이야기

1. 물통 (bucket) 크기가 A인 물통과 크기가 B인 물통이 있고, 처음에는 모든 물통이 비어있다. 아래 4가지 동작을 통해 크기가 A인 물통에는 P 만큼, 크기가 B인 물통에는 Q 만큼의 물을 담는 최소 동작 횟수를 구하는 문제다. 1) 크기가 A인 물통을 비우거나 가득 채운다. 2) 크기가 B인 물통을 비우거나 가득 채운다. 3) 크기가 A인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 B인 물통이 가득 차면 옮기는 것을 멈춘다. 4) 크기가 B인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 A인 물통이 가득 차면 옮기는 것을 멈춘다. 크기가 A인 물통에 a만큼의 물이, 크기가 B인 물통에 b만큼의 물이 담겨 있는 상태를 (a, b)라고 나타내자. 초기 상태나..

문제 링크 I. Robot 로봇은 초기에 동쪽을 바라보고 있고, $(0, 0)$ 위치에 있다. 회전하는 명령과 앞으로 이동하는 명령이 주어졌을 때, 주어진 정사각형 범위를 벗어나는지 아닌지 확인하고 벗어나지 않으면 최종 위치를 출력하는 문제다. 단순한 구현 문제이므로 설명은 생략한다. #include using namespace std; int yy[] = {0, -1, 0, 1}, xx[] = {1, 0, -1, 0}; int M, N; int y, x, dir; int main() { scanf("%d%d", &M, &N); for (int i=1;i M || x > M){ puts("-1"); return 0; } } printf("%d %d\n", x, y); } G. Percolation $M ..

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를 잡는다. 2. 정점 $x$에서 가장 먼 정점 $y$를 찾는다. 3. 정점 $y$에서 가장 먼 정점 $z$를 찾는다. 트리의 지름은 정점 $y$와 정점 $z$를 연결하는 경로다. 증명) 트리에서 정점 $u$와 정점 $v$를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 $x$를 정하고, 정점 $x$에서 가장 먼 정점 $y$를 찾았을 때, 아래와 같이 경우를 나눌 수 있다. i. $x$가 $u$ 혹은 $v$인 경우 ii. $y$가 $u$ 혹은 $v$인 경우 iii. $x$, $y$, $u$, $v$가 서..