블로그 언저리인 무언가

문제 : 13703 물벼룩의 생존확률 13703번: 물벼룩의 생존확률 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 www.acmicpc.net 1초마다 1/2 확률로 위 또는 아래로 이동할 때, 시간이 끝날 때까지 생존해있는 경우의 수를 구하면 된다. 수면에 닿았을 때 남은 움직임과 상관없이 모두 실패하고 남은 움직임 횟수보다 더 깊이 있는 상태에서는 2^횟수만큼 성공하므로 memoization기법을 활용해 Top-Down 방식의 DP를 짜서 이전 결과 값을 저장해 꺼내서 출력했다. Code #include #define ll long long using na..