알고리즘
[알고리즘 문제해결전략] SNAIL - 달팽이
[생각의 흐름] 1. 비오는날(75%)와 비가오지 않는날(25%)을 구분한다. 2. 비오는날과 비가오지 않는 날의 확률을 각각 곱하면서 목적지 (n)에 도달할 때까지 반복해 본다. => 완전탐색 3. 중복되는 경로의 확률을 메모이제이션 한다. 4. m일 안에 목적지 n에 도달했을 경우 1을 리턴하여 모든 경로의 확률을 곱하고 그렇지 않은 경우 0을 리턴하여 경우를 무효화 시킨다. 5. 절대 도달할 수 없는 경우( 예) 1000미터 우물을 100일 안에 도달)는 sol함수를 호출하지 않고 수식으로 가지치기 한다. /* https://www.algospot.com/judge/problem/read/SNAIL */ #include const int MAX_DAYS = 1001; const int MAX_MET..
