wbluke
commented
5 years ago [My Point]
- 입력도 무지막지하고, 생각해야 할 변수도 많아서 겁먹었었는데, 한 번에 정답 나와서 매우 뿌듯듯듯듯. 전공 그래프론 시간에 그래프 그리던게 이 문제에서 이렇게 도움이 되다니... 그리고 DP는 정말 많이 익숙해졌다고 봐도 될 것 같다. 부분문제 정의만 잘 잡을 수 있다면 적용 자체엔 문제가 없는 듯!
- 정의한 부분문제 P(n ,k) : n번째 날에 k번 마을에 두니발 박사가 있을 확률 차수 = 한 마을에 연결된 길의 개수 (그래프 이론) m번 마을의 인덱스를 Vm이라 할 때 P(n, k) = ( (1.0 / k마을과 연결된 Vm마을의 차수) * P(n-1, k마을과 연결된 Vm) )들의 합
https://algospot.com/judge/problem/read/NUMB3RS
APSS_p269