https://www.acmicpc.net/problem/12746 12746번: Traffic (Large) 사람들이 가장 많이 이용하는 구간을 출력하고, 몇 명의 사람들이 그 구간을 거쳤는지 출력한다. a b c 꼴로 출력하면 되는데, 이는 사람들이 가장 많이 이용하는 구간이 a번 역과 b번 역을 연결하 www.acmicpc.net 필요한 배경지식 최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍 문제 해결 방법 이전에 포스팅한 농장 관리 문제에서 풀이한 방법과 같은 방법을 이용하여 철로를 지난 사람의 수를 구할 수 있습니다. 농장 관리 문제와 다른점은 업데이트가 모두 이루어진 후 결과값을 출력하기 때문에, 노드에 추가되는 가중치를 배열에 누적하여 저장하고 DP로 문제를 해결할 수 있습니다. ..
https://www.acmicpc.net/problem/11960 11960번: Max Flow Farmer John has installed a new system of N−1 pipes to transport milk between the N stalls in his barn (2≤N≤50,000), conveniently numbered 1…N. Each pipe connects a pair of stalls, and all stalls are connected to each-other www.acmicpc.net 필요한 배경지식 최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍 문제 해결 방법 이전에 포스팅한 농장 관리 문제에서 ..
백준 14267번 - 회사 문화 1
https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 필요한 배경지식 트리에서의 다이나믹 프로그래밍 문제 해결 방법 문제를 읽어보면 직원들의 관계가 트리형태로 이루어져 있다는 것은 충분히 확인할 수 있습니다. 또한 i번째 직원이 받은 총 칭찬의 수는 i번째 직원이 직속 상사로부터 받은 칭찬과 i번째 직원을 부하로 가지는 모든 직원들이 직속 상사로부터 받은 칭찬을 더한 값이라고 볼 수 있습니다. 예시로 아래와 같은 트리를 살펴 봅시다. i번째 직원이..