King of the Jungle Lion

문제링크:14942번: 개미 (acmicpc.net) 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net 이 문제는 루트가 1인 n개의 노드를 가진 트리가 있을 때, 각 노드에서 무조건 루트 방향(조상노드방향) 으로 이동한다고 했을 때, 그리고 갈 수 있는 거리가 한정되어 있을 때 출발 해서 도달할 수 있는 최대 조상 노드를 구하는 문제이다. 이 문제는 얼마 전에 푼 LCA문제에서 이진 탐색을 이용한 희소 배열을 이용해서 조상 노드로 이동하는 원리를 사용했다. 먼저 dfs를 통해 루트(노드0)부터 탐색..

문제링크:2618번: 경찰차 (acmicpc.net) 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 이 문제의 조건은 먼저 경찰차가 두대 있는데 초기에 한대는 (1,1) 다른 한대는 (N,N) 좌표에 위치한다. 앞으로 W개의 사건들이 벌어지는데, 각 사건마다 사건의 좌표(X,Y) 가 주어진다. 경찰차 한대가 사건을 처리하러 가야 하고, 출동한 경찰차는 그 다음 사건까지 그 사건의 위치에서 대기한다. 여기서 경찰차가 움직인 거리는 만약 (1,1)의 경찰차가 간다면 |X-1|+|Y-1| ..

문제링크:1948번: 임계경로 (acmicpc.net) 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 이 문제의 조건은 먼저 n개의 노드와 m개의 가중치가 있는 일방향 간선들이 있을때, 임의의 시작 노드와 도착 노드가 정해 졌을 때에 시작 노드로부터 도착 노드로까지의 가장 큰 가중치의 합을 가진 경로를 찾고, 그 경로에 사용된 간선들의 개수를 반환하는 문제이다. 문제의 조건으로는 당연히 간선들 사이에 사이클은 존재하지 않고, 가장 큰 가중치 합을 가진 경로는 여러 개 일 수 있다는..

문제링크: 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 트리의 지름을 구하는 문제이다. 특징으로는 이 문제에서 주어지는 트리는 항상 간선의 개수가 노드의 개수-1 개 만큼 있다는 것이다. 사실 이미 1167번: 트리의 지름 문제를 이미 풀어 보았기 때문에 이 문제는 쉽게 풀 수 있었다. 1167번 문제는 트리의 노드, 간선의 개수가 자유롭게 주어져 고려해야 할 것이 더 많은 문제이다. 트리의 지름을 구하는 방법은 일단 한 노드에서 가중치..