https://www.acmicpc.net/problem/25198
문제 요약
- 트리가 주어짐
- S -> C -> H 로 이동
- 경로 순서대로 두 지점에서 닭다리 구매 가능. 경우의 수 구하기
- 경로에서 경우의 수를 바로 구하는 쉬운문제 아닌가 생각할 수 있는데, 주어진 예시를 보면 중복이 존재함
접근법
- 완전탐색은 힘듬
- 문제가 되는 경우가 SC 구간에서 하나, CH 구간에서 하나 구할때 중복이 발생함
- SC 구간 자체로는 중복이 발생하지 않음. 유일한 경로이니까
- CH 구간 자체로도 마찬가지임
- DFS를 이용하면 구간 경로 정보를 구할 수 있음
- (1,2,3,5), (5,3,4)
- 닭다리를 구매할 수 있는 경우는 다음과 같음
- SC 구간에서 : (1,2,3,5)에서 두개 => 6가지
- CH 구간에서 : (5,3,4)에서 두개 => 3가지
- SC에서 하나, CH에서 하나 : 4 * 3가지???? => 중복이 있어서 빼줘야함
- (3, 5)는 양쪽에 다 있음
- SC에서 (3,5)를 고르더라도 중복, CH에서 (3,5)를 고르더라도 중복
- 양쪽 구간에서 빼줌 : (1,2), (4)
- 그리고 경우의 수를 구하면 : 2 * 1 가지
- 6 + 3 + 2 = 11 가지
newbieski