본문 바로가기

Tree8

[백준 Silver 3] 9372 상근이의 여행 - Java 문제링크 : https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 접근 과정 : 문제의 접근 방법은 크게 두가지라고 생각한다. 먼저 지나가는 국가를 체크하면서 비행기를 타고, 모든 국가를 다 지나갔을 때, 비행기의 종류를 리턴하는 방법! 그런데 여기에는 약간의 함정이 있다. 국가를 여러번 지나가도 되고, 하나의 비행기를 여러번 타도 된다.!! 즉, 비행기의 종류(간선)이 최소가 되게 모든 국가를 연결하는 것인데 .. 2022. 1. 3.
[백준 Gold 3] 11812 K진 트리 - Java 문제링크 : https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 접근 과정 : 트리에서 부모 인덱스로 자식 인덱스를 계산하고, 자식 인덱스로 부모 인덱스를 계산하는 방식을 사용했다. 흔히 이진트리에서는 자식/2가 부모 인덱스가 되는 것처럼 이를 이용해 계산하려고 했다. 자식 인덱스를 보고 부모의 인덱스를 계산할 수 있는 방식이 필요했다. 나는 여려 계산 끝에, 부모 = (자식+K-2)/.. 2022. 1. 3.
[백준 Gold 5] 1068 트리 - Java 문제링크 : https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 접근 과정 : 트리에 속한 노드 중 하나를 삭제했을 때, 남아있는 리프노드의 갯수를 구하는 문제이다. 노드를 삭제하면 그 노드의 자식 노드들도 같이 삭제된다. 우선 자식노드를 저장하는 List 를 생성했다. 그리고 삭제할 노드부터 그 이하 자식노드를 모두 boolen[] removed에 체크했다. 이제 0번 노드부터 N-1번 노드까지 순회하면서, 현재 리프노드인 것만 계산했다. .. 2021. 12. 27.
[백준 Gold 2] 14657 준오는 최종인재야!! - Java 문제링크 : https://www.acmicpc.net/problem/14657 14657번: 준오는 최종인재야!! 첫째 줄에 문제의 수 N, 하루 풀이 시간 T가 주어진다. (2 ≤ N ≤ 50,000, 1 ≤ T ≤ 100,000) 이후 둘째 줄 부터 N-1개의 줄에 걸쳐 각 줄마다 A, B, C가 주어진다. (1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000) A와 B는 www.acmicpc.net 접근 과정 : 먼저 가장 많은 문제를 푸는 경우(트리의 지름)을 찾아야 한다.!! + 가장 많은 문제를 푸는 경우가 여러개 존재한다면, 가장 시간이 짧은 것을 찾아야 한다.!! 즉, 가장 긴 트리의 지름 중에서 가장 가중치가 적은 경우를 찾고 이를 기준으로 다시 한번 조회해서, 정확한 가중치를 찾아서 반.. 2021. 12. 21.

티스토리툴바