[usaco] 2.3 Controlling Companies - usaco
2009.08.24 00:19 Edit
2.3의 마지막 문제는 회사를 지배하는 순환구조를 이해해서 지주회사를 찾는 문제이다.
실제로 재벌회사인 삼성의 경우
다음과 같은 구조로 에버랜드를 통해 모든 삼성 계열사를 지배하고 있다고 한다.
출처 : 구글 이미지 검색
이런 지배관계가 주어질 때 어떤 회사가 어떤 회사를 50% 넘게 주식을 가지고 있으면 지배회사라고 할 수 있는데
그러한 지배회사 관계를 모두 찾는 문제이다.
문제의 풀이는 DFS와 DP를 조금 섞어서 풀어야 하는 문제이다.
나는 DP로만 풀려고 며칠 고민했지만 결국 정답을 보고 나서야 아 그렇구나 하고 작성했다.
실제로 재벌회사인 삼성의 경우
다음과 같은 구조로 에버랜드를 통해 모든 삼성 계열사를 지배하고 있다고 한다.
출처 : 구글 이미지 검색
이런 지배관계가 주어질 때 어떤 회사가 어떤 회사를 50% 넘게 주식을 가지고 있으면 지배회사라고 할 수 있는데
그러한 지배회사 관계를 모두 찾는 문제이다.
문제의 풀이는 DFS와 DP를 조금 섞어서 풀어야 하는 문제이다.
나는 DP로만 풀려고 며칠 고민했지만 결국 정답을 보고 나서야 아 그렇구나 하고 작성했다.
