트리 (4) 썸네일형 리스트형 [Softeer] [21년 재직자 대회 본선] 거리 합 구하기 / problemid 635 [JAVA] 문제링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=635&sw_prbl_sbms_sn=39796 Softeer Problem을 담을 Box를 선택해 주세요. 취소 확인 softeer.ai 모든 노드간 연결돼 있고 간선이 N-1개인 그래프는 트리다 모든 노드마다 다른 모든 노드와 거리의 합을 구한다면 N이 최대 2*10^5 이므로 단순하게는 불가능 해보인다 1번 노드를 루트로 하고 노드간 거리의 합을 먼저 구해보자 1번 노드를 루트로 하는 트리 1번에서 3번,5번,6번 노드로 가기 위해서는 빨간 간선을 지나가야 한다. 그러므로 빨간 간선은 2*3인 6을 정답값에 더해주는 간선이다. 마찬가지로 가중치가 5인 간선은 노드 2만을 위해 지나는 .. [프로그래머스] 2021 dev-matching 다단계 칫솔 판매 [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr (전처리) enroll 순서대로 해당 이름을 1~N까지 고유 번호를 HashMap에 저장했다. 또, referral 배열 정보로 해당 유저의 부모의 번호를 par 배열에 저장했다. seller 정보와 amount를 가지고 최초 이득 유저와 돈을 가지고서 다단계 과정을 수행했다. while문이 그것이며, 해당 코인을 본인에게 더하고 부모에게 넘겨주는 식이다. .. [해커랭크] Roads and Libraries [JAVA] 문제링크: www.hackerrank.com/challenges/torque-and-development/problem Roads and Libraries | HackerRank Help the ruler of HackerLand determine the cheapest way to give his citizens access to libraries. www.hackerrank.com 모든 노드들을 잇는 최소한의 간선 개수는 노드의 갯수 -1이다. 그래서 도로를 고쳐서 도서관을 공유하는 비용을 최소한 하려면 도로를 N-1개만 고치면 된다. (MST 구성) 고장난 도로를 탐색해서 노드가 몇개인지 파악하기 위해 dfs 탐색을 했다. 또, N-1개의 도로의 수리비용보다 모든 노드에 도서관을 설치하는 비용이 적.. [백준] 15681 트리와 쿼리 문제링크: www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 너무 많이 풀어본 유형이라 쉬웠다. 문제 설명이 아주 구체적이어서 그래프와 트리의 개념을 이해하기에 좋고, 그것을 실습 해보는 목적으로 풀기에 좋은 문제인 것 같다. import java.io.*; import java.util.*; public class Main { public static int N,R,Q; public static .. 이전 1 다음
